题解 | #跳台阶#

跳台阶

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

递归

class Solution {
public:
    int jumpFloor(int n) {
        if (n == 1) return 1;
        if (n == 2) return 2;
        return jumpFloor(n-1) + jumpFloor(n-2);
    }
};

动态规划

class Solution {
public:
    int jumpFloor(int n) {
        int dp[50];
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; ++i) {
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n];
    }
};

空间压缩

class Solution {
public:
    int jumpFloor(int n) {
        if (n == 1 || n == 2) return n;
        int step1 = 1;
        int step2 = 2;
        int step_n = 0;
        for (int i = 3; i <= n; ++i) {
            step_n = step1 + step2;
            step1 = step2;
            step2 = step_n;
        }
        return step_n;
    }
};

2023-剑指-DP 文章被收录于专栏

2023-剑指-DP

全部评论

相关推荐

点赞 收藏 评论
分享
牛客网
牛客企业服务