动态规划-数字三角形1

题目要求

在上面的数字三角形中寻找一条从顶部到底边的路径(注意是底边),使得路径上经过的数字之和最大.路径上的每一步都只能往左下或右下走.只需要求出这个最大和即可,不必给出具体路径.(三角形的行数大于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;
}