数字三角形

coding>C++
635 词

题目描述

1
2
3
4
5
7 
3 8 
8 1 0
2 7 4 4
4 5 2 6 5 

图一表示一个5行的数字三角形。假设给定一个n行数字三角形,计算出从三角形顶至底的一条路径，使该路径经过的数字总和最大。 每一步只能由当前位置向下或向右下。

输入

你的程序要能接受标准输入。第一行包含一个整数T，表示总的测试次数。 
对于每一种情况：第一行包含一个整数N,其中1 < N < 100,表示三角形的行数。 
接下来的N行输入表示三角形的每一行的元素Ai,j，其中0 < Ai,j < 100。

输出

输出每次测试的最大值并且占一行。

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<iostream>
using namespace std;
int map[102][102], d[102][102];
int main() {
    int T, n;
    cin >> T;
    while (T--) {
        cin >> n;
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= i; j++) {
                cin >> map[i][j];
                d[i][j] = map[i][j];
            }
        for (int i = n; i > 1; i--)
            for (int j = 1; j < i; j++)
                d[i - 1][j] = max(d[i][j + 1], d[i][j]) + map[i - 1][j];
        cout<<d[1][1];
    }
    return 0;
}