only_matthew @ 2021-10-10 16:40:44
“我从那里来”得分33
#include<cstdio>
#include<algorithm>
const int MAXN=1000+5;
int dp[MAXN][MAXN],w[MAXN][MAXN],r;
int main(){
scanf("%d",&r);
for(int i=1;i<=r;i++)
for(int j=1;j<=i;j++)
scanf("%d",&w[i][j]);
for(int i=1;i<=r;i++){
for(int j=1;j<=i;j++){
dp[i][j]=w[i][j]+std::max(dp[i-1][j],dp[i-1][j-1]);
}
}
printf("%d",dp[r][r]);
return 0;
}
“我到那里去”AC
#include<cstdio>
#include<algorithm>
const int MAXN=1000+5;
int dp[MAXN][MAXN],w[MAXN][MAXN],r;
int main(){
scanf("%d",&r);
for(int i=1;i<=r;i++)
for(int j=1;j<=i;j++)
scanf("%d",&w[i][j]);
for(int i=r;i>0;i--){
for(int j=1;j<=i;j++){
dp[i][j]=w[i][j]+std::max(dp[i+1][j],dp[i+1][j+1]);
}
}
printf("%d",dp[1][1]);
return 0;
}
by lailai0916 @ 2021-10-10 16:41:16
by danaqi @ 2021-10-10 16:52:34
最后一列取最值
by huwanpeng @ 2021-10-10 16:52:52
@only_matthew
最高点到底部任意处结束的路径
你第一个代码
dp[i][j]=w[i][j]+std::max(dp[i-1][j],dp[i-1][j-1]);
是从下往上累加