计蒜客CS109DP习题：捡水果

本文主要是介绍计蒜客CS109DP习题：捡水果，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

蒜头在玩一款游戏，他在一个山顶，现在他要下山，山上有许多水果，蒜头每下一个高度就可以捡起一个水果，并且获得水果的能量。

山的形状如图所示：

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

这是一个高度为 $4$ 的山，数字代表水果的能量。每次下一个高度，蒜头需要选择是往左下走，还是往右下走。例如：对于上图的情况，蒜头能获得的最大能量为，$3+1+6+5=15$。现在，蒜头希望你能帮他计算出下山能获得的最大能量。

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;
}

这篇关于计蒜客CS109DP习题：捡水果的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！