# 小朋友学算法（9）：深入理解动态规划

2018-02-03 10:20:27来源:https://www.jianshu.com/p/70235f80f8ca作者:翡翠森林Z人点击

http://poj.org/problem?id=1163

1.png

``5      //这一行的数字表示三角形行数，下面几行输入三角形73   88   1   02   7   4   44   5   2   6   5``

``if ( N == row)                      MaxSum(row, col) = num(row, col)    else        MaxSum(row, col) = Max{ MaxSum(row＋1, col), MaxSum(row + 1, col + 1) } + num(row, col)``

``#include <iostream>#include <algorithm>using namespace std;#define MAX 101int num[MAX][MAX];int n;int MaxSum(int row, int col){    if(n == row)    {        return num[row][col];    }    return max(MaxSum(row + 1, col), MaxSum(row + 1, col + 1)) + num[row][col];}int main(){    int row, col;    cin >> n;    for(row = 1; row <= n; row++)    {        for(col = 1; col <= row; col++)        {            cin >> num[row][col];        }    }    cout << MaxSum(1,1) << endl;}``

``573 88 1 02 7 4 44 5 2 6 530``

MaxSum(1, 1) = max(MaxSum(2, 1) + MaxSum(2, 2)) + num(1, 1)
MaxSum(2, 1) = max(MaxSum(3, 1) + MaxSum(3, 2)) + num(2, 1)
MaxSum(3, 1) = max(MaxSum(4, 1) + MaxSum(4, 2)) + num(3, 1)
MaxSum(4, 1) = max(MaxSum(5, 1) + MaxSum(5, 2)) + num(4, 1)
MaxSum(5, 1)直接返回4
MaxSum(5, 2)直接返回5
MaxSum(4, 2) = max(MaxSum(5, 2) + MaxSum(5, 3)) + num(4, 2)
MaxSum(5, 2)直接返回5
MaxSum(5, 3)直接返回2
MaxSum(3, 2) = max(MaxSum(4, 2) + MaxSum(4, 3)) + num(3, 2)
MaxSum(4, 2) = max(MaxSum(5, 2) + MaxSum(5, 3)) + num(4, 2)
MaxSum(5, 2)直接返回5
MaxSum(5, 3)直接返回2
MaxSum(4, 3) = max(MaxSum(5, 3) + MaxSum(5, 4)) + num(4, 3)
MaxSum(5, 3)直接返回2
MaxSum(5, 4)直接返回6
MaxSum(2, 2) = max(MaxSum(3, 2) + MaxSum(3, 3)) + num(2, 2)
MaxSum(3, 2) = max(MaxSum(4, 2) + MaxSum(4, 3)) + num(3, 2)
MaxSum(4, 2) = max(MaxSum(5, 2) + MaxSum(5, 3)) + num(4, 2)
MaxSum(5, 2)直接返回5
MaxSum(5, 3)直接返回2
MaxSum(4, 3) = max(MaxSum(5, 3) + MaxSum(5, 4)) + num(4, 3)
MaxSum(5, 3)直接返回2
MaxSum(5, 4)直接返回6
MaxSum(3, 3) = max(MaxSum(4, 3) + MaxSum(4, 4)) + num(3, 3)
MaxSum(4, 3) = max(MaxSum(5, 3) + MaxSum(5, 4)) + num(4, 3)
MaxSum(5, 3)直接返回2
MaxSum(5, 4)直接返回6
MaxSum(4, 4) = max(MaxSum(5, 4) + MaxSum(5, 5)) + num(4, 4)
MaxSum(5, 4)直接返回6
MaxSum(5, 5)直接返回5

2.png

（一）记忆递归

``#include <iostream>#include <algorithm>using namespace std;#define MAX 101int num[MAX][MAX];int n;int maxSum[MAX][MAX];int MaxSum(int row, int col){    if(-1 != maxSum[row][col])    {        return maxSum[row][col];    }    if(n == row)    {        maxSum[row][col] = num[row][col];    }    return max(MaxSum(row + 1, col), MaxSum(row + 1, col + 1)) + num[row][col];}int main(){    int row, col;    cin >> n;    for(row = 1; row <= n; row++)    {        for(col = 1; col <= row; col++)        {            cin >> num[row][col];            maxSum[row][col] = -1;        }    }    cout << MaxSum(1,1) << endl;}``

（二）优化方案一（递推）

（1）把最后一行直接写出

*****
*****
*****
*****
45265

（2）倒数第2行
maxSum[4][1] = max(2 + 4, 2 + 5) = 7
maxSum[4][2] = max(7 + 5, 7 + 2) = 12
maxSum[4][3] = max(4 + 2, 4 + 6) = 10
maxSum[4][4] = max(4 + 6, 4 + 5) = 10

*****
*****
*****
7121010*
45265

（3）倒数第3行
maxSum[3][1] = max(8 + 7, 8 + 12) = 20
maxSum[3][2] = max(1 + 12, 1 + 10) = 13
maxSum[3][3] = max(0 + 10, 0 + 10) = 10

*****
*****
201310**
7121010*
45265

（4）倒数第4行
maxSum[2][1] = max(3 + 20, 3 + 13) = 23
maxSum[2][2] = max(8 + 13, 8 + 10) = 21

*****
2321***
201310**
7121010*
45265

（5）倒数第5行
max[1][1] = max(7 + 23, 7 + 21) = 30

30****
2321***
201310**
7121010*
45265

``#include <iostream>#include <algorithm>using namespace std;#define MAX 101int num[MAX][MAX];int n;int maxSum[MAX][MAX];int main(){    int row, col;    cin >> n;    for(row = 1; row <= n; row++)    {        for(col = 1; col <= row; col++)        {            cin >> num[row][col];        }    }    for(int col = 1; col <= n; col++)    {        maxSum[n][col] = num[n][col];    }    for(int row = n - 1; row >= 1;  row--)    {        for( int col = 1; col <= row; col++)        {            maxSum[row][col] = max(maxSum[row + 1][col], maxSum[row + 1][col + 1]) + num[row][col];        }    }    cout << maxSum[1][1] << endl;}``

（三）优化方案二（一维数组）

int maxSum[101][101]总共占用了101 * 101 * 4 = 40804B = 40kB的内存空间。如果只用一维数组来存储结果的话，int maxSum[101] 总共只需占用101 * 4 = 404B的内存空间。

（1）最后一行原始数据

45265

（2）第四行第一列的最大值放在maxSum[1]中

75265

（3）第四行第二列的最大值放在maxSum[2]中

712265

（4）第四行第三列的最大值放在maxSum[3]中

7121065

（5）第四行第四列的最大值放在maxSum[4]中

71210105

（6）第三行第一列的最大值放在maxSum[1]中

201210105

（7）第三行第二列的最大值放在maxSum[2]中

201310105

（8）第三行第三列的最大值放在maxSum[3]中

201310105

（9）第二行第一列的最大值放在maxSum[1]中

231310105

（10）第二行第一列的最大值放在maxSum[2]中

232110105

（11）第一行第一列的最大值放在maxSum[2]中

302110105

``#include <iostream>#include <algorithm>using namespace std;#define MAX 101int num[MAX][MAX];int n;int maxSum[MAX];int main(){    int row, col;    cin >> n;    for(row = 1; row <= n; row++)    {        for(col = 1; col <= row; col++)        {            cin >> num[row][col];        }    }    for(int col = 1; col <= n; col++)    {        maxSum[col] = num[n][col];    }    for(int row = n - 1; row >= 1; row--)    {        for(int col = 1; col <= row; col++)        {            maxSum[col] = max(maxSum[col], maxSum[col + 1]) + num[row][col];        }    }    cout << maxSum[1] << endl;}``

（四）优化方案三（不用额外数组）

``#include <iostream>#include <algorithm>using namespace std;#define MAX 101int num[MAX][MAX];int n;int *maxSum;int main(){    int row, col;    cin >> n;    for(row = 1; row <= n; row++)    {        for(col = 1; col <= row; col++)        {            cin >> num[row][col];        }    }    maxSum = num[n];    for(int row = n - 1; row >= 1; row--)    {        for(int col = 1; col <= row; col++)        {            maxSum[col] = max(maxSum[col], maxSum[col + 1]) + num[row][col];        }    }    cout << maxSum[1] << endl;}``