$$\color{red}{算法}\color{blue}{基础课}\color{purple}{笔记and题解}\color{green}{汇总}$$

$$数字三角形$$

这道题和这道题有点像
这是一道经典DP题
这个也是一样：
对于$a_{x,y}$，只能从$a_{x-1,y}$和$a_{x-1,y-1}$转移而来。
所以状态转移方程就是：$f_{x,y}=max(f_{x-1,y},f_{x-1,y-1})+a_{x,y}$。

还要注意有个坑点：就是数值有可能是负数。

代码：（还是边读入边处理）

#include <bits/stdc++.h>
using namespace std;
int n, a[510][510];
int main() {
    scanf("%d", &n);
    for (int i = 1;i <= n; i++)
        for (int j = 0;j <= n + 1; j++) a[i][j] = -10000000; //两边也要设为负数。
    for (int i = 1;i <= n; i++)
        for (int j = 1;j <= i; j++) {
            scanf("%d", &a[i][j]);
            a[i][j] += max(a[i - 1][j], a[i - 1][j - 1]);
        }
    int ans = -10000000;
    for (int i = 1;i <= n; i++) ans = max(ans, a[n][i]);  //统计ans
    printf("%d\n", ans);
    return 0;
}