先看一道北大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）把最后一行直接写出
| * | * | * | * | * |
|---|---|---|---|---|
| * | * | * | * | * |
| * | * | * | * | * |
| * | * | * | * | * |
| 4 | 5 | 2 | 6 | 5 |
（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
| * | * | * | * | * |
|---|---|---|---|---|
| * | * | * | * | * |
| * | * | * | * | * |
| 7 | 12 | 10 | 10 | * |
| 4 | 5 | 2 | 6 | 5 |
（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
| * | * | * | * | * |
|---|---|---|---|---|
| * | * | * | * | * |
| 20 | 13 | 10 | * | * |
| 7 | 12 | 10 | 10 | * |
| 4 | 5 | 2 | 6 | 5 |
（4）倒数第4行
maxSum[2][1] = max(3 + 20, 3 + 13) = 23
maxSum[2][2] = max(8 + 13, 8 + 10) = 21
| * | * | * | * | * |
|---|---|---|---|---|
| 23 | 21 | * | * | * |
| 20 | 13 | 10 | * | * |
| 7 | 12 | 10 | 10 | * |
| 4 | 5 | 2 | 6 | 5 |
（5）倒数第5行
max[1][1] = max(7 + 23, 7 + 21) = 30
| 30 | * | * | * | * |
|---|---|---|---|---|
| 23 | 21 | * | * | * |
| 20 | 13 | 10 | * | * |
| 7 | 12 | 10 | 10 | * |
| 4 | 5 | 2 | 6 | 5 |
代码实现：
#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）最后一行原始数据
| 4 | 5 | 2 | 6 | 5 |
|---|
（2）第四行第一列的最大值放在maxSum[1]中
| 7 | 5 | 2 | 6 | 5 |
|---|
（3）第四行第二列的最大值放在maxSum[2]中
| 7 | 12 | 2 | 6 | 5 |
|---|
（4）第四行第三列的最大值放在maxSum[3]中
| 7 | 12 | 10 | 6 | 5 |
|---|
（5）第四行第四列的最大值放在maxSum[4]中
| 7 | 12 | 10 | 10 | 5 |
|---|
（6）第三行第一列的最大值放在maxSum[1]中
| 20 | 12 | 10 | 10 | 5 |
|---|
（7）第三行第二列的最大值放在maxSum[2]中
| 20 | 13 | 10 | 10 | 5 |
|---|
（8）第三行第三列的最大值放在maxSum[3]中
| 20 | 13 | 10 | 10 | 5 |
|---|
（9）第二行第一列的最大值放在maxSum[1]中
| 23 | 13 | 10 | 10 | 5 |
|---|
（10）第二行第一列的最大值放在maxSum[2]中
| 23 | 21 | 10 | 10 | 5 |
|---|
（11）第一行第一列的最大值放在maxSum[2]中
| 30 | 21 | 10 | 10 | 5 |
|---|
代码实现：
#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;
}
注意，优化方案二和优化方案三，都只是节省空间，不能节省时间。
更多内容请关注微信公众号
feicuisenlin_12x12.jpg
网友评论