题解 | #不能连续吃草的牛#
不能连续吃草的牛
https://www.nowcoder.com/practice/64d9400c321042acb754a9455852a8d7
知识点
一维线性动态规划
思路
第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;
}
};