題目要求

在上面的數(shù)字三角形中尋找一條從頂部到底邊的路徑(注意是底邊),使得路徑上經(jīng)過的數(shù)字之和最大.路徑上的每一步都只能往左下或右下走.只需要求出這個最大和即可,不必給出具體路徑.(三角形的行數(shù)大于1小于等于100,數(shù)字為0-99)

輸入格式

5  //三角形行數(shù),下面是三角形,走正下方或者右下方
7
38
810
2744
45265

解題思路

用二維數(shù)組存放數(shù)字三角形
D(r,j):第r行第j個數(shù)字(r,j從1開始算)
MaxSum(r,j):從D(r,j)到底邊的各條路徑中,最佳路徑的數(shù)字之和.
問題,求MaxSum(1,1)
典型的遞歸問題
D(r,j)出發(fā),下一步只能走D(r+1,j)或者D(r+1,j+1).故對于N行的三角形:

if(r==N)
    MaxSum(r,j) = D(r,j)
else
    //也就是第一個數(shù)字加上正下方或者右下方最大的數(shù)字
    MaxSum(r,j) = Max{ MaxSum(r+1,j) },MaxSum(r+1,j+1) + D(r,j)

但這種方法太慢,因為其中有許多重復計算,時間復雜度2的n次方O(2^n)
被調(diào)用次數(shù)如下圖

改進

如果每計算出一個MaxSum(r,j)就保存起來,下次用到其值的時候直接取用,則可免去重復計算.那么可以用O(n^2)時間完成計算.因為三角形的數(shù)字總數(shù)是n(n+1)/2

數(shù)字三角形的記憶遞歸型動歸程序

#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,則已經(jīng)計算過,這里避免重復計算
    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;
}