题解 | #跳台阶#

算法思路

由于青蛙在每一层台阶都只存在两种跳法：选择跳一级还是两级。那么假设跳上n级台阶有F(n)中跳法，很容易就可以写出递推公式

F(n) = F(n - 1) + F(n - 2);

这不就是动态规划中的状态转移方程么，因此代码就很容易写出来了。

算法实现一

首先用递归方式实现：

public class Solution {
    public int jumpFloor(int target) {
        if (target <= 1) {
            return 1;
        }

        return jumpFloor(target - 1) + jumpFloor(target - 2);
    }
}

这种方式有个很严重的问题就是存在重复计算问题：每次计算出F(n)后都没有保存，下次还得重新计算，因此就有下面这个版本。

算法实现二

要在计算过程中，保存计算过的值，那么就不能从n到1递归计算了，而应该是从1到n搜索，这便是记忆化搜索：

public class Solution {
    public int jumpFloor(int target) {
        if (target <= 1) {
            return 1;
        }

        // 数组A保存跳n级台阶存在的跳法数量
        int[] A = new int[target + 1];
        A[0] = A[1] = 1;
        for (int i = 2; i <= target; i++) {
            A[i] = A[i - 1] + A[i - 2];
        }
        return A[target];
    }
}