題目重述
描述
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
(圖1)

圖1給出了一個數(shù)字三角形。從三角形的頂部到底部有很多條不同的路徑。對于每條路徑，把路徑上面的數(shù)加起來可以得到一個和，你的任務(wù)就是找到最大的和。

注意：路徑上的每一步只能從一個數(shù)走到下一層上和它最近的左邊的那個數(shù)或者右邊的那個數(shù)。
輸入
輸入的是一行是一個整數(shù)N (1 < N <= 100)，給出三角形的行數(shù)。下面的N行給出數(shù)字三角形。數(shù)字三角形上的數(shù)的范圍都在0和100之間。
輸出
輸出最大的和。
樣例輸入
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
樣例輸出
30
來源
openjudge 2760

解題思路

用二維數(shù)組來存放數(shù)字三角形：D[r][j]表示第r行第j個數(shù)字（r,j從1開始算）
maxsum(r,j)：從D[r][j]到底邊的各條路徑中，最佳路徑的數(shù)字之和
問題：求maxsum（1,1）

1.典型的遞歸問題
D[r][j]出發(fā)，下一步只能走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列的數(shù)字
int n;//三角形列數(shù)
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];
}

這個程序的壞處：
進(jìn)行了大量的重復(fù)計算，當(dāng)數(shù)值大時將會超時。
假設(shè)三角形有5行，則計算的次數(shù)如下圖所示（紅色數(shù)字代表計算次數(shù)）

5364899301874B31965D61F0296DE010.jpg

將每一行的紅色數(shù)字加起來，可得出它的時間復(fù)雜度為2^n。
計算量是巨大的。

2.改進(jìn)版（1）
記憶遞歸型動規(guī)

思路：每算出來一個maxsum(r,j)之后就把它的值保存起來，當(dāng)下次要用到該值的時候直接取用，就可以避免重復(fù)計算了，由于三角形的數(shù)字總數(shù)為n(n+1)/2。所以完成計算的時間復(fù)雜度為O(n^2)
記憶遞歸型動規(guī)程序如下：

#include <iostream>
#define Max  101
using namespace std;
int n;//三角形行數(shù) 
int D[Max][Max];//第i行第j列的數(shù)字
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){
    //已經(jīng)計算過從第i行第j列到底部的最大值，直接拿來用，避免重復(fù)計算
    if(MaxSum[i][j] != -1)
        return MaxSum[i][j];
    
    if(i == n)//已經(jīng)到底部了 
        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.改進(jìn)版（2）
使用遞推
MaxSum[][]這個數(shù)組是來存放最大值的
將遞歸轉(zhuǎn)化為遞推：先將數(shù)組的最后一行MaxSum[n][i]初始化：
MaxSum[n][i] = D[n][i]
然后再從后面遞推上去

1.png

從i = n-1行開始遍歷，從第1列開始，取第j列的max{正下方數(shù)字和右下方數(shù)字}（即max{MaxSum[i+1][j],MaxSum[i+1][j+1]}，然后再將D[i][j]和此最大值相加，以此類推就可以得出來結(jié)果：

2.png

MaxSum[1][1]就是我們想要的答案（數(shù)組行和列都從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.改進(jìn)版（3）
空間優(yōu)化

沒必要用二維數(shù)組MaxSum來存儲每一個maxsum(r,j)，從底層一行行向上遞推，只需要一個一維數(shù)組MaxSum[100]即可，即只要存儲一行的maxsum值就可以

如果進(jìn)一步考慮的話，可以連MaxSum數(shù)組都不要。直接用D的第n行替代maxsum即可。
該改進(jìn)節(jié)省了空間，時間復(fù)雜度不變