线性DP问题-数字三角形详解

把三角形状态表示成二维数组：

fij就是所有从起点走到ij的路径

分状态：一类来自左上方，一类来自右上方
左上方：f(i-1,j-1)+aij
右上方：f(i-1,j)+aij

正序算法

C++ 代码

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 510,INF=1e9;
int n;
int a[N][N],f[N][N];

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]=-INF;//初始化到各个点的距离为无穷

    f[1][1]=a[1][1];//因为11点的最大值已经确定
    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]);//带入DP方程

    int res = -INF;
    for(int i=1;i<=n;i++) res=max(res,f[n][i]);//最大值都集中在每一行的最右边，所以在其中找最大的ni即可
    printf("%d\n",res);
    return 0;
}

倒序算法

C++ 代码

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 510;
int n;
int w[N][N],f[N][N];

int main(){
    cin>>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            cin>>w[i][j];
    for(int i=1;i<=n;i++)f[n][i]=w[n][i];
    for(int i=n-1;i;i--)
        for(int j=1;j<=i;j++)
            f[i][j]=max(f[i+1][j]+w[i][j],f[i+1][j+1]+w[i][j]);
    cout<<f[1][1]<<endl;

    return 0;
}