题解 | #贪吃牛#
贪吃牛
https://www.nowcoder.com/practice/ae6261c872724fda8913b0377e85f6ab
考察的知识点:动态规划;
解答方法分析:
- 定义状态:dp[i]表示吃完i块草料的不同方式数量。
- 初始化状态:dp[0] = 1,dp[1] = 1,因为当n=0时,牛已经吃完了,所以只有一种方式。当n=1时,牛只能吃1块草料,也只有一种方式。
- 状态转移方程:根据题目描述,牛可以选择吃1块或者2块草料,所以dp[i] = dp[i - 1] + dp[i - 2],即前一次的方式加上前两次的方式之和。
- 计算结果:使用一个循环计算dp数组的值,最终结果就是dp[n]。
所用编程语言:C++;
完整编程代码:↓
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param n int整型
* @return int整型
*/
int eatGrass(int n) {
vector<int> dp(n + 1, 0);
dp[0] = 1;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
};

