算法训练 数字三角形

问题描述 　　（图３.１－１）示出了一个数字三角形。 请编一个程序计算从顶至底的某处的一条路 　　径，使该路径所经过的数字的总和最大。 　　●每一步可沿左斜线向下或右斜线向下走； 　　●1＜三角形行数≤100； 　　●三角形中的数字为整数0，1，…99； 　　 . 　　（图３.１－１） 输入格式 　　文件中首先读到的是三角形的行数。 　　接下来描述整个三角形 输出格式 　　最大总和（整数） 样例输入 5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 样例输出

30

问题分析：动态规划，倒着走从下往上进行讨论，因为若要路径值最大，那么上一层的dp[i][j]一定会加上下一层dp[i+1][j]与dp[i+1][j+1]中的最大值，一层层的走，dp[i][j]表示经过i,j时从下往上的路径最大值，一直走到第一层，即dp[0][0]即为路径最大值

一开始用的dfs做的，虽然答案正确，但是会超时

#include<stdio.h> #include<string.h> #include<iostream> using namespace std; int dp[110][110]; int main() { int row; memset(dp,0,sizeof(dp)); scanf("%d",&row); for(int i=0; i<row; i++) for(int j=0; j<=i; j++) { scanf("%d",&dp[i][j]); } for(int i=row-2; i>=0; i--) { for(int j=0; j<=i; j++) { if (dp[i+1][j]>dp[i+1][j+1]) dp[i][j] += dp[i+1][j]; else dp[i][j] += dp[i+1][j+1]; } } printf("%d\n",dp[0][0]); return 0; }