题目
Description
给定一个数塔,其存储形式为如下所示的下三角矩阵。在此数塔中,从顶部出发,在每一节点可以选择向下走还是向右下走,一直走到底层。请找出一条路径,使路径上的数值和最大。
Input
多组输入,EOF结束,对于每组输入第一行为一个数字n表示数塔的高度,之后为n行,每行有1,2,3...n个数字(数字范围-100到100),表示数塔中的数字
Output
对于每组输入输出一行,表示最大值。
Sample Input
5
9
12 15
10 6 8
2 18 9 5
19 7 10 4 16Sample Output
59
题解
动态规划问题,将东西输入后
从下往上刷(n-1 ~ 0)。计算到大第i层的第j个位置的最大值
dp[i][j] = dp[i][j] + max(dp[i+1][j],dp[i+1][j+1])
即每一个位置应该与能到达它的最大位置相加
最后dp[0][0]
就是答案
#代码
/* By:OhYee Github:OhYee HomePage:http://www.oyohyee.com Email:oyohyee@oyohyee.com Blog:http://www.cnblogs.com/ohyee/ かしこいかわいい? エリーチカ! 要写出来Хорошо的代码哦~ */ #include <cstdio> #include <algorithm> #include <cstring> #include <cmath> #include <string> #include <iostream> #include <vector> #include <list> #include <queue> #include <stack> #include <map> #include <set> using namespace std; const int maxn = 1000; int Map[maxn][maxn]; bool Do() { int n; if(scanf("%d",&n) == EOF) return false; memset(Map,0,sizeof(Map)); for(int i = 1;i <= n;i++) for(int j = 1;j <= i;j++) scanf("%d",&Map[i][j]); for(int i = n - 1;i > 0;i--) for(int j = 1;j <= i;j++) Map[i][j] += max(Map[i + 1][j],Map[i + 1][j + 1]); printf("%d\n",Map[1][1]); return true; } int main() { while(Do()); return 0; }