动态规划（DP）之入门学习-数字三角形_数字三角形动态规划一维dp

数字三角形案例

题目描述 Description

下图给出了一个数字三角形，请编写一个程序，计算从顶至底的某处的一条路径，使该路径所经过的数字的总和最大。
（1）每一步可沿左斜线向下或右斜线向下
（2）1 < 三角形行数 < 100
（3）三角形数字为0，1，…99

输入描述 Input Description

有很多个测试案例，对于每一个测试案例， 通过键盘逐行输入，第1行是输入整数（如果该整数是0,就表示结束，不需要再处理），表示三角形行数n，然后是n行数

输出描述 Output Description

输出最大值。

样例输入 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

递归解法

解题思路

用二维数组存放数字三角形。
D( r, j) : 第r行第 j 个数字(r,j从1 开始算)
MaxSum(r, j) : 从D(r,j)到底边的各条路径中，最佳路径的数字之和。
问题：求 MaxSum(1,1)
典型的递归问题。
D(r, j)出发，下一步只能走D(r+1,j)或者D(r+1, j+1)。故对于N行的三角形：

if ( r == N)
 MaxSum(r,j) = D(r,j)
else
 MaxSum( r, j) = Max{ MaxSum(r＋1,j), MaxSum(r+1,j+1) } + D(r,j)
1
2
3
4

代码实现

#include <iostream>
#include <algorithm>

#define Max 101

using namespace std;

int D[Max][Max];

int num;

int MaxSum(int i, int j){
    if(i == num)
        return D[i][j];
    int x = MaxSum(i + 1, j);
    int y = MaxSum(i + 1, j + 1);
    return max(x,y) + D[i][j];
}

int main(int argc, char const *argv[])
{
    int i, j;

    cin >> num;

    for(i = 1; i <= num; i 
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