输入样例：
5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5输出样例：
30 从上往下推： 使用一维数组，每次输入的值用num存储，输入后与上一个值相比，加上大者，最后直接找数组中的最大值即可。a[1] a[2] a[3] a[4] a[5] a[6]
第一次： 0 0 0 0 7 0
第二次： 0 0 0 10 15 0
第三次： 0 0 18 16 15 0
第四次： 0 20 25 20 19 0
第五次： 24 30 27 26 24 0
#include <iostream> using namespace std; int a[1000000]; int main() { int ans = 0,num,n; cin >> n; for(int i = n ; i > 0 ; i--) { for(int j = i; j <= n ; j++) { cin >> num; a[j] = max(a[j],a[j+1]) + num; } } for(int i = 1; i <= n ; i++) { ans = max(ans,a[i]); } cout << ans << endl; return 0; } 从下往上推 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5从倒数第二行开始，2+4 = 6 < 2+5 = 7；7+5 = 12 > 7+2 = 9…… 转移为a[i][j] += max(a[i+1][j+1],a[i+1][j])
#include <iostream> using namespace std; int dp[1010][1010]; int main() { int n; cin >> n; for(int i = 0 ; i < n ; i++) { for(int j = 0 ; j <= i; j++) { cin >> dp[i][j]; } } for(int i = n - 2; i >= 0; i--) { for(int j = 0 ; j <= i ; j++) { dp[i][j] += max(dp[i+1][j+1],dp[i+1][j]); } } cout << dp[0][0]; return 0; }