动态规划之数字三角形
题目重述
描述
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
(图1)
图1给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径，把路径上面的数加起来可以得到一个和，你的任务就是找到最大的和。
注意：路径上的每一步只能从一个数走到下一层上和它最近的左边的那个数或者右边的那个数。
输入
输入的是一行是一个整数N (1 < N <= 100)，给出三角形的行数。下面的N行给出数字三角形。数字三角形上的数的范围都在0和100之间。
输出
输出最大的和。
样例输入
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
样例输出
30
来源
openjudge 2760
解题思路
用二维数组来存放数字三角形：D[r][j]表示第r行第j个数字（r,j从1开始算）
maxsum(r,j)：从D[r][j]到底边的各条路径中，最佳路径的数字之和
问题：求maxsum（1,1）
1.典型的递归问题
D[r][j]出发，下一步只能走D[r+1][j] 或者D[r+1][j+1]
所以可得出递归模型：
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];
程序代码：
#include <iostream>
using namespace std;
int MaxSum(int i,int j);//求第i行第j列到底边的最大值
int maxs(int x,int y);//返回最大值
int D[101][101];//第i行第j列的数字
int n;//三角形列数
int main(){
cin >> n;
for(int i=1;i<=n;++i)
for(int j=1;j<=i;++j)
cin >> D[i][j];
cout << MaxSum(1,1) << endl;
return 0;
}
int maxs(int x,int y){
return (x > y?x: y);
}
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 maxs(x,y) + D[i][j];
}
这个程序的坏处：
进行了大量的重复计算，当数值大时将会超时。
假设三角形有5行，则计算的次数如下图所示（红色数字代表计算次数）
5364899301874B31965D61F0296DE010.jpg
将每一行的红色数字加起来，可得出它的时间复杂度为2^n。
计算量是巨大的。
2.改进版（1）
记忆递归型动规
思路：每算出来一个maxsum(r,j)之后就把它的值保存起来，当下次要用到该值的时候直接取用，就可以避免重复计算了，由于三角形的数字总数为n(n+1)/2。所以完成计算的时间复杂度为O(n^2)
记忆递归型动规程序如下：
#include <iostream>
#define Max 101
using namespace std;
int n;//三角形行数
int D[Max][Max];//第i行第j列的数字
int MaxSum[Max][Max];//从第i行第j列到底部的最大值
int maxsum(int i,int j);//计算从第i行第j列到底部的最大值
int maxs(int x,int y);//返回2者中最大值
int main(){
cin >> n;
//i和j从1开始
for(int i=1;i<=n;++i)
for(int j=1;j<=i;++j){
cin >> D[i][j];
MaxSum[i][j] = -1;//赋初值-1
}
cout << maxsum(1,1) << endl;
return 0;
}
int maxsum(int i,int j){
//已经计算过从第i行第j列到底部的最大值，直接拿来用，避免重复计算
if(MaxSum[i][j] != -1)
return MaxSum[i][j];
if(i == n)//已经到底部了
MaxSum[i][j] = D[i][j];
else{
int x = maxsum(i+1,j);
int y = maxsum(i+1,j+1);
MaxSum[i][j] = maxs(x,y) + D[i][j];
}
return MaxSum[i][j];
}
int maxs(int x,int y){
return (x > y ? x : y);
}
3.改进版（2）
使用递推
MaxSum[][]这个数组是来存放最大值的
将递归转化为递推：先将数组的最后一行MaxSum[n][i]初始化：
MaxSum[n][i] = D[n][i]
然后再从后面递推上去
1.png
从i = n-1行开始遍历，从第1列开始，取第j列的max{正下方数字和右下方数字}（即max{MaxSum[i+1][j],MaxSum[i+1][j+1]}，然后再将D[i][j]和此最大值相加，以此类推就可以得出来结果：
2.png
MaxSum[1][1]就是我们想要的答案（数组行和列都从1开始算）
程序代码：
#include <iostream>
#define Max 101
using namespace std;
int n;
int D[Max][Max];//第i行第j列的值
int MaxSum[Max][Max];//第i行第j列到底边的最大值
int maxs(int x,int y);//返回两者的最大值
int main(){
cin >> n;
for(int i=1;i<=n;++i)
for(int j= 1;j<=i;++j)
cin >> D[i][j];
for(int i=1;i<=n;++i)
MaxSum[n][i] = D[n][i];//赋初值
for(int i=n-1;i>=1;--i)
for(int j = 1;j<=n;++j)
MaxSum[i][j] = maxs(MaxSum[i+1][j],MaxSum[i+1][j+1]) + D[i][j];
cout << MaxSum[1][1] << endl;
return 0;
}
int maxs(int x,int y){
return (x > y ? x : y);
}
4.改进版（3）
空间优化
没必要用二维数组MaxSum来存储每一个maxsum(r,j)，从底层一行行向上递推，只需要一个一维数组MaxSum[100]即可，即只要存储一行的maxsum值就可以
如果进一步考虑的话，可以连MaxSum数组都不要。直接用D的第n行替代maxsum即可。
该改进节省了空间，时间复杂度不变
