AcWing 898. 数字三角形

/*

    算法1：DP  （自上而下）      时间复杂度 O(n2 )

    解题思路：
    不妨把等腰三角形拉伸成直角三角形，方便存储和坐标分析。

    状态表示： f(i,j) 表示 所有 自上而下 到（i,j）点的路线     取到的最大数字和
    状态转移： f(i,j) = max( f(i-1,j), f(i-1,j+1) ) + a[i][j]

    即：自上而下走的时候，对每个点，可以从正上方或右上方下来，取较大值，再加上点本身的数字即可。
*/
#include<bits/stdc++.h>
using namespace std;

const int N=510,INF=1e9;

int f[N][N];
int a[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=1;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],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;
}

/*
算法2：DP  （自下而上）      时间复杂度 O(n2 )

    解题思路：

    状态表示： f(i,j) 表示 所有 自下而上 到（i,j）点的路线     取到的最大数字和
    状态转移： f(i,j) = max( f(i+1,j), f(i+1,j+1) ) + a[i][j]

    即：自上而下走的时候，对每个点，可以从正下方或右下方上来，取较大值，再加上点本身的数字即可。
*/
#include<bits/stdc++.h>
using namespace std;

const int N=510,INF=1e9;

int f[N][N];
int a[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=1;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+1],f[i+1][j])+a[i][j];
        }
    }

    cout<<f[1][1]<<endl;
}