AcWing 898. 数字三角形
原题链接
简单
作者:
烧仙草
,
2021-01-21 10:28:37
,
所有人可见
,
阅读 356
本题同样是线性dp题。
用二维数组dp[N][N]来存取到每一个子节点的最大值。
同时需要注意的是,因为负数的存在,dp中的数要先开成-INF。
下面给出代码
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=600;
int p[N][N];
int dp[N][N];
int n;
int main(){
memset(dp,-1e4-10,sizeof dp);
cin>>n;
for(int i=0;i<n;i++){
for(int j=1;j<=i+1;j++){
cin>>p[i][j];
}
}
dp[0][1]=p[0][1];
for(int i=1;i<n;i++){
for(int j=1;j<=i+1;j++){
dp[i][j]=max(dp[i-1][j]+p[i][j],dp[i-1][j-1]+p[i][j]);
}
}
int res=-1e4-10;
for(int u=1;u<=n;u++){
res=max(res,dp[n-1][u]);
}
cout<<res<<endl;
}