题解 | #跳台阶#

跳台阶

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];
}

全部评论

相关推荐

10-10 16:30
济宁学院 Java
一表renzha:面试官:蓝桥杯三等奖?你多去两次厕所都能拿二等吧
点赞 评论 收藏
分享
用微笑面对困难:只要你保证项目和获奖都是真的就行尤其是“对战,总负责人”啊这些套职,基本上队员,打杂的都这么写
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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