思路
由于每一行的最大路径数字和都是要从上一行的最大路径数字和求出,就像背包问题一样逐行求状态表示(就像每次加一个物品一样)来解决这道题
代码一 (优化成一维的)
#include <iostream>
using namespace std;
const int N = 510;
int f[N];
int main(){
int n; scanf("%d", &n);
for(int i = 0; i <= n; i ++ )
f[i] = -1e9;
//因为输入会有负数,所以要把路径和设为绝对值较大的负数
f[1] = 0;
for(int i = 1; i <= n; i ++ )
for(int j = i; j >= 1; j -- ){
int x; scanf("%d", &x);
f[j] = max(f[j-1]+x, f[j]+x);
}
int ans = -1e9;
for(int i = 1; i <= n; i ++ )
ans = max(ans, f[i]);
printf("%d", ans);
return 0;
}
算法2 (二维—未经优化)
#include <iostream>
using namespace std;
const int N = 510;
int w[N][N];
int main(){
int n; scanf("%d", &n);
for(int i = 0; i <= n; i ++ )
for(int j = 0; j <= i+1; j ++ )
w[i][j] = -1e9;
w[0][1] = 0;
for(int i = 1; i <= n; i ++ )
for(int j = 1; j <= i; j ++ ){
int x; scanf("%d", &x);
w[i][j] = max(w[i-1][j-1]+x, w[i-1][j]+x);
}
int ans = -1e9;
for(int i = 1; i <= n; i ++ )
ans = max(ans, w[n][i]);
printf("%d", ans);
return 0;
}