线性DP

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

   1 2 3 4 5

反推:
$res=max\langle {(5,1),(5,2),(5,3),(5,4),(5,5)\rangle}$

$(5,4)=max\langle {(4,4),(4,3)\rangle}+w$

状态数组：$F[N][N]$

状态转换方程：$F[i][j]=max(F[i-1][j],F[i-1][j-1])+w$

C++ 代码

#include<bits/stdc++.h>

using namespace std;

const int INF=0x3f3f3f3f,N=510;

int f[N][N];

int main(){
    int n;
    cin>>n;
    for(int i=0;i<=n;i++){
        for(int j=0;j<=n;j++){
            f[i][j]=-INF;
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            f[i][j]=-INF;
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=i;j++){
            cin>>f[i][j];
        }
    }
    int res=-INF;
    for(int i=2;i<=n;i++){
        for(int j=1;j<=i;j++){
            f[i][j]+=max(f[i-1][j],f[i-1][j-1]);
            if(i==n)res=max(res,f[i][j]);
        }
    }
    cout<<res;
    return 0;
}