题解 | #贪吃牛#

贪吃牛

https://www.nowcoder.com/practice/ae6261c872724fda8913b0377e85f6ab

一、知识点:

动态规划

二、文字分析:

用动态规划来解决。假设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];
    }
}

全部评论

相关推荐

头像
04-09 14:29
Java
点赞 评论 收藏
转发
点赞 收藏 评论
分享
牛客网
牛客企业服务