数字三角形

⬅ 返回

1、题目

2、闫氏DP分析法

2.1、一维

代码

#include<iostream>
using namespace std;
const int N = 1e6+10;
int dp[N];
int s[N];
int t[N],node=0;
 
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=i;j++)
        {
            node++;
            cin>>t[node];
            s[node]=i;
        }
    }
    
    for(int i=1;i<=node;i++)
    {
        dp[i]=-0x3f3f3f3f;
    }
    dp[1]=t[1];
    int res = -0x3f3f3f3f;
    for(int i=2;i<=node;i++)
    {
        //当前点的层次
        int k = s[i];
        //左父节点
        if(s[i-k]==k-1)
            dp[i]=dp[i-k]+t[i];
        if(s[i-k+1]==k-1)
            dp[i]=max(dp[i],dp[i-k+1]+t[i]);
    }
    for(int i=1;i<=node;i++)
    {
        if(s[i]==n)
        {
            res=max(res,dp[i]);
        }
    }
    cout<<res<<endl;
    
}

2.2、二维

代码

#include <iostream>
#include <algorithm>
 
using namespace std;
 
const int N = 510, INF = 1e9;
 
int n;
int t[N][N];
int dp[N][N];
 
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= i; j ++ )
            scanf("%d", &t[i][j]);
 
    for (int i = 0; i <= n; i ++ )
        for (int j = 0; j <= i + 1; j ++ )
            dp[i][j] = -INF;
 
    dp[1][1] = t[1][1];
    for (int i = 2; i <= n; i ++ )
        for (int j = 1; j <= i; j ++ )
            dp[i][j] = max(dp[i - 1][j - 1] + t[i][j], dp[i - 1][j] + t[i][j]);
 
    int res = -INF;
    for (int i = 1; i <= n; i ++ ) res = max(res, dp[n][i]);
 
    printf("%d\n", res);
    return 0;
}