线性DP：数字三角形

题目描述

输入样例

5
7
3 8
8 1 0 
2 7 4 4
4 5 2 6 5

输出样例

30

参考代码

#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;const int N = 510;int n;          // 三角形的层数
int a[N][N];    // 存储输入的数
int f[N][N];    // 集合：f[i][j]表示从(1, 1)到(i, j)所有的方案集合；属性：路径长度Max// 上一步是左上方的点：f[i][j] = f[i - 1][j - 1] + a[i][j]   
// 上一步是右上方的点：f[i][j] = f[i - 1][j] + a[i][j]int main()
{scanf("%d", &n);for (int i = 1; i <= n; i++)for (int j = 1; j <= i; j++) scanf("%d", &a[i][j]);for (int i = 0; i <= n; i++)for (int j = 0; j <= i + 1; j++) f[i][j] = -0x3f3f3f3f;// 不能初始化为0，因为输入有负数f[1][1] = a[1][1];for (int i = 2; i <= n; i++)for (int j = 1; j <= i; j++)f[i][j] = max(f[i - 1][j - 1], f[i - 1][j]) + a[i][j];int ans = -0x3f3f3f3f;for (int i = 1; i <= n; i++) ans = max(ans, f[n][i]);printf("%d\n", ans);return 0;
}