题目要求
在上面的数字三角形中寻找一条从顶部到底边的路径(注意是底边),使得路径上经过的数字之和最大.路径上的每一步都只能往左下或右下走.只需要求出这个最大和即可,不必给出具体路径.(三角形的行数大于1小于等于100,数字为0-99)
输入格式
5 //三角形行数,下面是三角形,走正下方或者右下方
7
38
810
2744
45265
解题思路
用二维数组存放数字三角形
D(r,j):第r行第j个数字(r,j从1开始算)
MaxSum(r,j):从D(r,j)到底边的各条路径中,最佳路径的数字之和.
问题,求MaxSum(1,1)
典型的递归问题
D(r,j)出发,下一步只能走D(r+1,j)或者D(r+1,j+1).故对于N行的三角形:
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)
但这种方法太慢,因为其中有许多重复计算,时间复杂度2的n次方O(2^n)
被调用次数如下图
改进
如果每计算出一个MaxSum(r,j)就保存起来,下次用到其值的时候直接取用,则可免去重复计算.那么可以用O(n^2)时间完成计算.因为三角形的数字总数是n(n+1)/2
数字三角形的记忆递归型动归程序
#include <iostream>
#include<algorithm>
using namespace std;
#define MAX 101
int D[MAX][MAX];
int n;
int maxSum[MAX][MAX];
int MaxSum(int i,int j)
{
//如果不是-1,则已经计算过,这里避免重复计算
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] = max(x,y) +D[i][j];
return maxSum[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]; //输入三角形
maxSum[i][j] = -1; //初始化为-1,表示最大路径还没有被算出来过
}
cout<<MaxSum(1,1)<<endl;
return 0;
}
