一、知识点:
动态规划
二、文字分析:
用动态规划来解决。假设dp[i]表示吃完i块草料的不同方式数量。对于当前的dp[i],考虑最后一次吃的草料数量,可以是1块或者2块。如果最后一次吃1块草料,那么前面就剩下了i-1块草料,即dp[i] = dp[i-1];如果最后一次吃2块草料,那么前面就剩下了i-2块草料,即dp[i] = dp[i-2]。所以总的不同方式数量就是dp[i] = dp[i-1] + dp[i-2]。
时间复杂度为O(n),空间复杂度也是O(n)
三、编程语言:
java
四、正确代码:
import java.util.*; public class Solution { public int eatGrass(int n) { int[] dp = new int[n+1]; dp[0] = 1; dp[1] = 1; for (int i = 2; i <= n; i++) { dp[i] = dp[i-1] + dp[i-2]; } return dp[n]; } }