遞歸之數字三角形問題

問題描述

在上面的數字三角形中尋找一條從頂部到底邊的路徑，使得路徑上所經過的數字之和最大。路徑上的每一步都隻能往左下或者右下走。隻需要求出這個最大和即可。不必給出具體路徑。

三角形的行數大于1小于等于100，數字為0-99

輸入格式

5 //三角形行數。下面是三角形

7

3 8

8 1 0

2 7 4 4

4 5 2 6 5

要求輸出最大和

遞歸解決算法思想

用二維數組存放數字三角形

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)

程式代碼

#include<iostream>
#include<algorithm>
using namespace std;
#define MAXSIZE 10
int n;
int d[MAXSIZE][MAXSIZE];
int maxSum(int r,int j){
	//當到了最下面一層的時候，就直接等于其值 
	if(r==n){
		return d[r][j];
	}else{
	//到底邊的最大路徑等于往下走的最大路徑和往右下走的最大路徑的最大值 
		int x=maxSum(r+1,j);
		int y=maxSum(r+1,j+1);
		return max(x,y)+d[r][j];
	} 
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=i;j++){
			cin>>d[i][j];
		}
	}
	cout<<maxSum(2,2);
	return 0;
}

           

遞歸解決問題分析

逾時?

為什麼逾時

7(1)

3(1) 8(1)

8(1) 1(2)

2(1) 7(3) 4(3) 4(1)

4(1) 5(4) 2(6) 6(4) 5(1)

回答：重複計算

例如，上面的程式，我們計算maxsum7的時候，會調用maxsum3和8各一次，而第三行的maxsum1會被調用2次，第四行的maxsum7會被調用3次，maxsum3也會被調用3次。把他們全部加起來就是2的n次方。

如果采用遞歸的辦法，深度周遊每條路徑，存在大量重複計算。則時間複雜度為2的n次幂，對于n=100,肯定逾時

改進

如果每算出一個maxsum(r,j)就儲存起來，下次用到其值的時候就直接去用，則可免去重複計算。那麼可以用o(n2)時間完成計算。因為三角形的數字總是n(n+1)/2。

遞歸解決問題改程序式代碼

#include<iostream>
#include<algorithm>
using namespace std;
#define MAXSIZE 10
int n;
int d[MAXSIZE][MAXSIZE];
int maxSum[MAXSIZE][MAXSIZE];		//存儲從某一點到最底邊的最大路徑值 
int MaxSum(int r,int j){
	if(maxSum[r][j]!=-1){
		return maxSum[r][j]; 
	}
	//當到了最下面一層的時候，就直接等于其值 
	if(r==n){
		maxSum[r][j]=d[r][j];
	}else{
	//到底邊的最大路徑等于往下走的最大路徑和往右下走的最大路徑的最大值 
		int x=MaxSum(r+1,j);
		int y=MaxSum(r+1,j+1);
		maxSum[r][j]=max(x,y)+d[r][j];
	} 
	return maxSum[r][j];
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=i;j++){
			cin>>d[i][j];
			//初始化maxsum數組，當未被計算時，其值為-1 
			maxSum[i][j]=-1;	
		}
	}
	cout<<MaxSum(2,2);
	return 0;
}