剑指10 II：跳台阶

传送门

nowcoder
leetcode

题目描述

一次可以跳上 1 级台阶，也可以跳上 2 级。
求跳上一个 n 级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

C++ 代码 - nowcoder

/*
    递归写法，超时
*/
class Solution {
public:
    int jumpFloor(int num) {
        if (num == 1) return 1;
        if (num == 2) return 2;
        return jumpFloor(num - 1) + jumpFloor(num - 2);
    }
};

/*
    状态表示：
        f[i] 表示上一个 i 级的台阶有多少种跳法。
    状态计算：
        f[i] = f[i - 1] + f[i - 2], i >= 2
    初始化：
        f[0] = 1, f[1] = 1;
    
    时间复杂度：O(n)
    空间复杂度：O(n)
*/
class Solution {
public:
    const int N = 40;
    
    int jumpFloor(int num) {
        if (num == 1)  return 1;
        if (num <= 2)  return num;

        int f[N + 1];
        f[0] = 1, f[1] = 1;
        for (int i = 2; i <= num; i ++) {
            f[i] = (f[i - 1] + f[i - 2]);
        }

        return f[num];
    }
};

/*
    优化空间：三个变量保存元素，来回替换

    时间复杂度：O(n)
    空间复杂度：O(1)
*/
class Solution {
public:
    int jumpFloor(int num) {
        if (num == 1) return 1;
        if (num <= 2) return num;

        int first = 1, second = 2;
        for (int i = 3; i <= num; i++) {
            int third = first + second;
            first = second;
            second = third;
        }
        return second;  
    }
};

C++ 代码 - leetcode

class Solution {
public:
    const int MOD = 1e9 + 7;

    int numWays(int n) {
        if (n == 0) return 1;
        if (n <= 2) return n;

        int f[n + 1];
        f[0] = 1, f[1] = 1;
        for (int i = 2; i <= n; i ++) {
            f[i] = (f[i - 1] + f[i - 2]) % MOD;
        }

        return f[n];
    }
};

/*
    优化空间：三个变量保存元素
*/
class Solution {
public:
    const int MOD = 1e9 + 7;

    int numWays(int n) {
        if (n == 0) return 1;
        if (n <= 2) return n;

        int f0 = 1, f1 = 1, f2 = 0;
        for (int i = 2; i <= n; i ++) {
            f2 = (f0 + f1) % MOD;
            f0 = f1;
            f1 = f2;
        }
        return f2;
    }
};