計蒜客CS109DP習題：撿水果

蒜頭在玩一款遊戲，他在一個山頂，現在他要下山，山上有許多水果，蒜頭每下一個高度就可以撿起一個水果，并且獲得水果的能量。

山的形狀如圖所示：

1          
3      
        
     2          
1 2      
        
     3          
6 2 3      
        
     4          
3 5 4 1      
   

這是一個高度為 44 的山，數字代表水果的能量。每次下一個高度，蒜頭需要選擇是往左下走，還是往右下走。例如：對于上圖的情況，蒜頭能獲得的最大能量為，3 + 1 + 6 + 5 = 153+1+6+5=15。現在，蒜頭希望你能幫他計算出下山能獲得的最大能量。

輸入格式

第一行輸入一個 nn，代表山的高度。（1 < n <= 10001<n<=1000）接下來 n 行，第 i+1i+1 行有 ii 個數字，代表水果的能量，水果能量為正整數且不大于 10001000。

輸出格式

輸出一個數字，代表下山一共獲得的最大能量，占一行。

樣例輸入

4
3
1 2
6 2 3
3 5 4 1      

樣例輸出

15      

首先用DFS的思想過一遍，從上往下周遊，每層dfs向下遞歸有兩種情況。需要傳遞和維護的是行列，以及上一層的最大能量結果。即

dfs(s_ij,i,j){

    dfs(s_ij+nl[i+1][j],i+1,j);

    dfs(s_ij+nl[i+1][j+1],i+1,j+1);

}

現在換用遞推的方式實作，從最上層往下循環即可，很簡單。核心代碼如下。

for(int i=1;i<=n;i++){

for(int j=1;j<=n;j++){

dp[i][j]=max(dp[i-1][j-1],dp[i-1][j])+nengliang[i][j];

}

}

附上源程式代碼：

#include<bits/stdc++.h>

using namespace std;

int  nengliang[1007][1007];
long long dp[1007][1007];

int main(void){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=i;j++){
			cin>>nengliang[i][j];
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			dp[i][j]=max(dp[i-1][j-1],dp[i-1][j])+nengliang[i][j];
		}
	}
	long long sum=0;
	for(int i=1;i<=n;i++){
		sum=max(dp[n][i],sum);
	}
	
	cout<<sum<<endl;
	
	return 0;
}