数字三角形问题【动态规划】

• Problem Description

给定一个由n行数字组成的数字三角形如下图所示。试设计一个算法，计算出从三角形的顶至底的一条路径，使该路径经过的数字总和最大。
对于给定的由n行数字组成的数字三角形，计算从三角形的顶至底的路径经过的数字和的最大值。

Input
输入数据的第1行是数字三角形的行数n，1≤n≤100。接下来n行是数字三角形各行中的数字。所有数字在0…99之间。
Output
输出数据只有一个整数，表示计算出的最大值。

Sample Input

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

Sample Output

30
1

• 样例分析

注：如图所示，这是样例的答案。

• 解题思路

我们首先想到的可能是从顶到底递归求解。从点(i , j)到下一层有两条路：（1）到达点(i+1, j)；（2）到达点(i+1, j+1)。选点的依据就是比较下一层的这两个点，看那个点上的数字大。重复操作，直至到达最底层。现在，我们反过来思考，从底到顶递归求解，只要修改一下for循环的条件即可。

• 代码实现

#include<bits/stdc++.h>
using namespace std;

const int Max=101;
int n;
int dp[Max][Max];   //dp[i][j]表示点(i,j)的上的数字

int maxSum(int n)   //maxSum(n)表示层数为 n 的三角形，从顶到底的数字总和的最大值
{
    for(int i=n-1;i>=1;i--)   //从底开始
    {
        for(int j=1;j<=i;j++)   //这里的dp[i][j]表示从底到点(i,j)的最大数字和
        {
            dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+dp[i][j];   //从下往上到达点(i,j)有两条路：（1）从点(i+1,j)到达；（2）从点(i+1,j+1)到达。选数字较大者
        }
    }
    return dp[1][1];   //从底到点(1,1)的最大数字和，即为所求值
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=i;j++)
            cin>>dp[i][j];
    }
    cout<<maxSum(n)<<endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

• 运行结果