題目重述
描述
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
上面給出了一個數字三角形。從三角形的頂部到底部有很多條不同的路徑。對于每條路徑，把路徑上面的數加起來可以得到一個和，你的任務就是找到最大的和。
注意：路徑上的每一步隻能從一個數走到下一層上和它最近的左邊的那個數或者右邊的那個數。
輸入
輸入的是一行是一個整數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行，則計算的次數如下圖所示（紅色數字代表計算次數）
将每一行的紅色數字加起來，可得出它的時間複雜度為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]
然後再從後面遞推上去
從i = n-1行開始周遊，從第1列開始，取第j列的max{正下方數字和右下方數字}（即max{MaxSum[i+1][j],MaxSum[i+1][j+1]}，然後再将D[i][j]和此最大值相加，以此類推就可以得出來結果：
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即可。
該改進節省了空間，時間複雜度不變