题解 | #不能连续吃草的牛#

知识点

一维线性动态规划

思路

第i天吃与不吃的选择，是由第i-1天和i-2天转移过来的。

如果第i天不吃，那么可以从第i-1天的吃或不吃转移过来

如果第i天吃，那么只能从第i-1天的不吃转移过来，此外还可以从第i-2天的吃转移过来。

不妨用dp[n][2]表示状态，dp[i][k]中，i表示第i天，k取值为0或1，分别表示吃与不吃，值为饱腹感。 有如下状态转移方程：

dp[i][0]=max(dp[i-1][1],dp[i-1][0]);

dp[i][1]=max(dp[i-1][0],dp[i-2][1])+nums[i];

初始化

整个dp数组初始化为0即可，因为一开始都是不吃的，饱腹感为0.

注意dp[1][0]=nums[0]，dp[1][1]=nums[1],dp[0][1]=nums[0]

代码c++

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return int整型
     */
    int eatGrass(vector<int>& nums) {
       int dp[10005][2];
memset(dp,0,sizeof dp);
       dp[0][1]=nums[0];
       dp[0][0]=0;
       dp[1][1]=nums[1];
       dp[1][0]=nums[0];
       int res=-1;
       int n=nums.size();
       for(int i=2;i<nums.size();i++)
       {
        dp[i][0]=max(dp[i-1][1],dp[i-1][0]);

        dp[i][1]=max(dp[i-1][0],dp[i-2][1])+nums[i];
       
        
       } 
       //for(int i=0;i<n;i++)cout<<dp[i][0]<<"  "<<dp[i][1]<<endl;
       res= max(dp[n-1][0],dp[n-1][1]);
       return res;
     
    }
};