题解 | #跳台阶#

首先可以看最基础的情况，一级台阶的时候只有一种跳法，两级台阶的时候有两种，11,2两种；

• 3级台阶，3级可以由1级台阶再跳2级来，也可以由2级再跳1级来， 假设f(x)代表x级台阶的跳动方法数，则f(3) = f(2) + f(1)
• 4级台阶，3级可以由2级台阶再跳2级来，也可以由3级再跳1级来， 假设f(x)代表x级台阶的跳动方法数，则f(4) = f(3) + f(2)

以此类推，f(x) = f(x - 1) + f(x - 2), x >= 3......

可以设一个长度为n + 1 的数组，数组dp[i] 代表跳动第i级有几种跳法，这样做空间复杂度为o(n),我们可以发现求当前数值只与前两个数值有关，与前面的所有都无关了，我们可以定义两个变量维护这两个值，在循环中不断改变值就行了。

代码如下：

public class Solution {
    public int jumpFloor(int target) {
       // 一只青蛙跳台阶，一次可以跳一级，也可以跳两级
        // 上n级台阶有几种跳法
        if(target <= 2) return target;
        int pre1 = 1;
        int pre2 = 2;
        int cur = 0;
        for(int i = 3; i <= target; i++){
            cur = pre1 + pre2;
            pre1 = pre2;
            pre2 = cur;
        }
        return cur;
    }
}