题解 | #跳台阶#

跳台阶

https://www.nowcoder.com/practice/8c82a5b80378478f9484d87d1c5f12a4

递归

int jumpFloor(int number) {
    if(number <= 1) return 1;
    return jumpFloor(number - 1) + jumpFloor(number - 2);
}

记忆化搜索

int f[50]{0};
int jumpFloor(int number) {
    if(number <= 1) return 1;
    if(f[number] > 0) return f[number];
    return f[number] = (jumpFloor(number - 1) + jumpFloor(number - 2));
}

动态规划

当n=0时 从0个台阶跳到0个台阶 就只有一种方法=》不跳 所以dp[0] = 1

为了保证在递推的时候不会出现数组越界情况

int dp[50]{0};
int jumpFloor(int number) {
    dp[0] = 1, dp[1] = 1;
    for(int i = 2; i <= number; i ++) dp[i] = dp[i - 1] + dp[i - 2];
    return dp[number];
}

全部评论

相关推荐

不愿透露姓名的神秘牛友
07-08 13:15
点赞 评论 收藏
分享
06-15 18:44
黄淮学院 Java
Lynn012:如果是居民楼还是算了吧,看着有点野呢
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务