一层一层的，有着模糊的线性关系，成为线性DP。
数字三角形：
复杂度：状态数量 * 转移，本题状态数量是n ^ 2 = 500 * 500 = 250000，转移是O(1)的。
#include <iostream> #include <algorithm> #include <cstring> using namespace std; const int N = 500, INF = 1e9; int a[N][N], f[N][N]; int main() { int n; cin>>n; for(int i = 1;i <= n;i++) for(int j = 1; j <= i; j++) cin>>a[i][j]; for(int i = 0; i <= n; i++) for(int j = 0; j <= i + 1; j++) f[i][j] = -INF; 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] + a[i][j], f[i-1][j] + a[i][j]); } int res = -INF; for(int i = 1;i<= n;i++) res = max(res, f[n][i]); cout<<res<<endl; }
1、因为有负数，所以不能默认就初始化为0，0不能作为最小数来进行比较。
2、初始化为负无穷的时候多初始化一列，因为到下一行最后一列的时候，f[i-1][j]的j实际上是上一行的i+1列。而第一行第一列的时候上一行的f[i-1][j-1]都是为0，所以赋值虽然是从1开始，但是初始化要从0开始，并且多一个结束。
从下至上：
#include <iostream> #include <algorithm> #include <cstring> using namespace std; const int N = 500, INF = 1e9; int a[N][N], f[N][N]; int main() { int n; cin>>n; for(int i = 1;i <= n;i++) for(int j = 1; j <= i; j++) cin>>a[i][j]; for(int i = 0; i <= n; i++) for(int j = 0; j <= i + 1; j++) f[i][j] = -INF; for(int i = 1; i <= n; i++) f[n][i] = a[n][i]; for(int i = n-1; i >= 1; i--) for(int j = 1; j<=i; j++) { f[i][j] = max(f[i+1][j] + a[i][j], f[i+1][j+1] + a[i][j]); } cout<<f[1][1]<<endl; }
原文：https://www.cnblogs.com/longxue1991/p/12747418.html