题解 | #跳台阶#

描述
一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
示例1
输入：
2
返回值：
2
示例2
输入：
7
返回值：
21

递归：

class Solution {
public:
    int jumpFloor(int number) {
        if (number < 2) return 1;  // 递归终止条件
        return jumpFloor(number-1) + jumpFloor(number - 2); // 递归实现
    }
};

动态规划：

class Solution {
public:
    int jumpFloor(int number) {
        if (number < 2) return 1;  // 初始条件
        else {
            vector<int> dp(number+1, 1); // 初始条件
            for (int i = 2; i <= number; ++i) {
                dp[i] = dp[i-1] + dp[i-2]; // 动态规划
            }
            return dp[number];
        }
    }
};

空间优化：

class Solution {
public:
    int jumpFloor(int number) {
        if (number < 2) return 1;  // 初始条件
        else {
            int dp1 = 1, dp2 = 1, dp; // 初始条件
            for (int i = 2; i <= number; ++i) {
                dp = dp1 + dp2;  // 动态规划
                dp2 = dp1;
                dp1 = dp;
            }
            return dp;
        }
    }
};