数字三角形问题路径值最大算法设计

一种常用的算法是动态规划。

1. 定义状态 设 $f(i,j)$ 表示从顶点 $i,j$ 出发到底边的最大路径和。

2. 状态转移方程 对于每个 $f(i,j)$，它可以从两个状态转移而来：

$$ f(i,j)=\max{f(i+1,j),f(i+1,j+1)}+a_{i,j} $$

其中，$a_{i,j}$ 表示第 $i$ 行第 $j$ 列的数字。

3. 初始状态 对于最后一行的每个数字 $a_{n,j}$，有 $f(n,j)=a_{n,j}$。

4. 最终答案 最终答案为 $f(1,1)$。

5. 代码实现

int f[N][N];
for (int j = 1; j <= n; j++) {
    f[n][j] = a[n][j];
}
for (int i = n - 1; i >= 1; i--) {
    for (int j = 1; j <= i; j++) {
        f[i][j] = max(f[i+1][j], f[i+1][j+1]) + a[i][j];
    }
}
int ans = f[1][1];
``