计蒜客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;
}