又写了次, 顺多了。
继续努力, 向 小媛在努力 学习。
#include <iostream> #include <string> using namespace std; int main() { int n, tri[101][101], dp[101][101], i, j, Max; while (scanf("%d", &n) != EOF) { memset(tri, 0, sizeof(tri)); for (i = 1; i <= n; i++) for (j = 1; j <= i; j++) scanf("%d", &tri[i][j]); memset(dp, 0, sizeof(dp)); //下往上推DP //for (i = n; i > 0; i--) // for (j = 1; j <= i; j++) // { // dp[i][j] = max(dp[i+1][j], dp[i+1][j+1]) + tri[i][j]; // //printf("i = %d j = %d dp[i][j] = %d\n", i, j, dp[i][j]); // } //printf("%d\n", dp[1][1]); //上往下推DP for (i = 1; i <= n; i++) for (j = 1; j <= i; j++) { dp[i][j] = tri[i][j] + max(dp[i-1][j-1], dp[i-1][j]); //printf("i = %d j = %d dp[i][j] = %d\n", i, j, dp[i][j]); } //最大值都存在了最后一行, 查找最大值输出 //还是下往上推理解方便, 代码也好写 Max = -100000; for (j = 1; j <= n; j++) Max = Max > dp[n][j] ? Max : dp[n][j]; printf("%d\n", Max); } return 0; }