题目

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 16

Sample 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;
}