线性dp

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 
 4 const int N = 520,INF = 1e9;
 5 int n;
 6 int a[N][N]; //表示每一个点
 7 int f[N][N]; //表示状态
 8 
 9 int main()
10 {
11     cin >> n;
12     for (int i = 1; i <= n; i ++ )
13        for (int j = 1; j <= i; j ++ )
14            cin >> a[i][j];
15     
16     for (int i = 0; i <= n; i ++ )
17        for (int j = 0; j <= i + 1; j ++ ) //每行多初始化一个，表示三角形最右边的右上角表示负无穷
18           f[i][j] = -INF; //避免处理边界情况，先将状态初始化为负无穷
19     
20     f[1][1] = a[1][1];
21     
22     for (int i = 2; i <= n; i ++ )
23        for (int j = 1; j <= i; j ++ )
24        f[i][j] = max(f[i - 1][j - 1] + a[i][j],f[i - 1][j] + a[i][j]);
25     
26     int res = -INF;   
27     for (int i = 1; i <= n; i ++ ) //枚举三角形底边终点的状态的最大值
28        res = max(res,f[n][i]);
29        
30     cout << res << endl;
31            
32     return 0;
33 }