小朋友学算法(9):深入理解动态规划

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

分享

先看一道北大POJ上的题:
http://poj.org/problem?id=1163




1.png

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


输入格式:


5      //这一行的数字表示三角形行数,下面几行输入三角形
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

要求输出最大和


一、递归实现

用num( row, col) 来表示第r行第 j 个数字(r,j从1开始算)
用MaxSum(row, col)表示从num(row, col)到底边的各条路径中,最佳路径的数字之和。
因此,此题的问题就变成了求 MaxSum(1,1)
从num(row, col)出发,下一步只能走num(row + 1, col)或者num(row + 1, col + 1)。故对于N行的三角形,我们可以写出如下的递归式子:


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 101
int 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;
}

运行结果:


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

这个程序提交上去会超时,因为递归会包含大量的重复计算。


具体的计算步骤如下:
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
二、动态规划
(一)记忆递归

每算出一个MaxSum(row, col)就保存起来,下次用到其值的时候直接取用,则可免去重复计算。那么可以用n方的时间复杂度完成计算,因为三角形的数字总数是 n(n+1)/2


#include <iostream>
#include <algorithm>
using namespace std;
#define MAX 101
int 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 101
int 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 101
int 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;
}

(四)优化方案三(不用额外数组)

上一步中的maxSum[]一维数组也可以不要,直接把每一行的最大值存到num[][]中的最后一行即可。


实现代码:


#include <iostream>
#include <algorithm>
using namespace std;
#define MAX 101
int 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;
}

注意,优化方案二和优化方案三,都只是节省空间,不能节省时间。





最新文章

123

最新摄影

闪念基因

微信扫一扫

第七城市微信公众平台