应用动态规划思想解决实际问题_动态规划解决实际问题

从概念和原理出发去学习某个知识点，往往有种晦涩、无从下手的感觉，本文列举两个示例，从实际应用的角度来理解“动态规划”思想。

数字三角形问题

“数字三角形”是动态规划的经典入门问题：

问题描述：
            7
          3   8
        8   1   0
      2   7   4   4
    4   5   2   6   5

给定一个数字三角形（例如上图），寻找一条从顶部到底边的路径，使得路径上所经过的数字之和最大。路径上的每一步都只能往左下或右下走。只需要求出这个最大和即可，不必给出具体路径。三角形的行数大于1且小于等于100，数字范围为0-99。

输入描述：第一行输入三角形的行数，接下来输入数字三角形
5            
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

输出描述：输出路径的最大和
30
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

分析：我们用一个二维数组来存储数字三角形，其中D[i][j]表示第i行第j个数字（i, j从1开始算）。用MaxSum(i, j)表示从D[i][j]到底边的各条路径中最佳路径的数字之和，所以本题即为求MaxSum(1, 1)，是一个典型的递归问题。

1.递归
由题意，当从D[i][j]出发时，下一步的选择只能是D[i + 1][j]或D[i + 1][j + 1]。所以，对于n行的三角形，可得到以下递归式：

// 如果D[i][j]就在底边，则其MaxSum的值即为它本身
if(i == n)
    MaxSum(i, j) = D[i][j]
// 如果D[i][j]不在底边，则其MaxSum的值为它左下和右下元素的MaxSum值的较大者加上它本身
else
    MaxSum(i, j) = Max{ MaxSum(i ＋ 1, j), MaxSum(i + 1, j + 1) } + D[i][j]
1
2
3
4
5
6

由此可写出“递归”思路的代码，如下：

#include <iostream>    
#include <algorithm>    
using namespace std;   

#define MAX 101 

int D[MAX][MAX];    
int n;    

int MaxSum(int i, int j)
{      
    if(i == n)    
        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 i, j;      
    cin >> n;      
    for(i = 1; i <= n; i++)     
        for(j = 1; j <= i; j++)          
            cin >> D[i][j];      
    cout << MaxSum(1,1) << 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

递归的思路简单，但由于存在大量重复计算，时间复杂度很高（O(2^n)）。例如下图，我们从第二行的数字3和8出发，求其到底边的最佳路径之和时，均需要计算一次第三行数字1到底边的最佳路径之和，重复计算浪费了时间。

2.记忆递归型的动态规划：