思路
从上到下比从下到上简单
不需要考虑特殊情况
闫式dp
第一种解法
#include<iostream>
#include<cstring>
using namespace std;
const int N=504;
int g[N][N],dp[N][N];
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=i;j++)
cin>>g[i][j];
for(int i=n-1;i>=1;i--)
for(int j=1;j<=i;j++)
g[i][j]+=max(g[i+1][j],g[i+1][j+1]);
cout<<g[1][1]<<endl;
return 0;
}
压缩数组把空间复杂度降到O(n)
滚动数组解法
#include<iostream>
#include<cstring>
using namespace std;
const int N=504;
int g[N][N],dp[N];
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=i;j++)
cin>>g[i][j];
for(int i=n;i>=1;i--)
for(int j=1;j<=i;j++)
dp[j]=max(dp[j+1],dp[j])+g[i][j];
cout<<dp[1]<<endl;
return 0;
}