题目简化即为从一个三角形数列的顶端沿对角线走到底端,所取得的和最大值
7
*
3 8
*
8 1 0
*
2 7 4 4
*
4 5 2 6 5 该走法即为最大值 分析:简单的动态规划,从上往下一层一层的考虑,对于每一行的最左边和最右边只有一种走法,只需要简单的相加,
对于中间的数要考虑是加上左上角的数还是加右上角的数,加上两者中的较大者 代码:
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAX_N = ;
int dp[MAX_N+][MAX_N+];
int n;
int main() {
scanf("%d", &n);
memset(dp, , sizeof(dp)); for(int i = ; i <= n; i++) {
for(int j = ; j < i; j++) {
scanf("%d", &dp[i][j]);
if(j == ) dp[i][j] += dp[i-][j];
else if(j == i - ) dp[i][j] += dp[i-][j-];
else dp[i][j] += max(dp[i-][j],dp[i-][j-]);
}
}
int ans = ;
for(int i = ; i < n; i++) ans = max(dp[n][i], ans);
printf("%d\n", ans);
return ;
}