描述

思路：

• 递归
• 动态规划

知识点：递归，动态规划

难度：⭐⭐

题解

图解：

图中圈出来的表示出现的重叠子问题，需要优化

方法一：递推

解题思路：

本题可以用自顶向下的递归方法，从一级台阶开始向上跳，那么想要跳到第n级台阶，由于题目要求一次能跳一级或二级台阶，因此要跳到n级台阶只能从n-1和n-2分别跳一级和二级台阶到达，可以得出结论：每一级台阶的跳法数量是下面的两级台阶的方法数之和。只需要注意定义递归函数功能和递归终止条件即可。

假设当前要跳上第 n 级台阶的跳法，必定是在第 n-1 和跳上 n-2 级台阶跳法数之和。

设跳上 i 级台阶有 f(n) 种跳法，则跳上 n 级台阶有 f(n) = f(n-1) + f(n-2)， 再结合考虑特殊情况，就有如下递推式:

算法流程：

• 定义递归函数功能：返回跳到第 target 级台阶的跳法数
• 递归终止条件：第一级台阶和第二级台阶分别有一种和两种跳法
• jumpFloor(target - 1) + jumpFloor(target - 2)表示每一级台阶的跳法数量是下面的两级台阶的方法数之和

Java 版本代码如下：

public class Solution {
	// 返回跳到第 target 级台阶的跳法数
    public int jumpFloor(int target) {
    	// 递归终止条件：第一级台阶和第二级台阶分别有一种和两种跳法
        if(target == 1 || target == 2) {
            return target;
        }
        // 自顶向下递归
        return jumpFloor(target - 1) + jumpFloor(target - 2);
    }
}

复杂度分析：

时间复杂度：$O(n^2)O(n^2)$，没有消除重叠子问题，每个节点会递归两次

空间复杂度：$O(n^2)O(n^2)$递归需要调用的栈空间

方法二：记忆化搜索

算法流程：

• 通过一个长度为 target + 1 的数组，保存每次计算结果，可以避免重复递归计算
• 由于数组的元素初始化都为0，对于memo[n] 为0的表示还未递归过，则进行计算后保存本次节点状态
• 如果 memo[n] != 0 ，则表示已经被计算过，直接访问即可，消除重叠子问题

Java 版本代码如下：

public class Solution {
    public int jumpFloor(int target) {
        // java默认初始化为0
        int[] memo = new int[target + 1];
        return f(target, memo);
    }
    
    public int f(int n, int[] memo) {
        if(n == 1 || n == 2) {
            return n;
        }
        // 表示已经访问过
        if(memo[n] != 0) {
            return memo[n];
        }
        // 保存状态
        memo[n] = f(n - 1, memo) + f(n - 2, memo);
        return memo[n];
    }
}

复杂度分析：

时间复杂度 O(N)：备忘录消除了重叠子问题

空间复杂度 O(N)：备忘录需要用到数组来保存已经遍历过的节点

方法三：动态规划

解题思路：

可以使用自底向上的动态规划方法，代码通过迭代实现，即跳到第 i 级台阶需要依靠第 i-1 和 i-2 级台阶的方法之和。

由于它可以跳1级台阶或者2级台阶，所以它上一步必定在第n-1,或者第n-2级台阶，也就是说它跳上n级台阶的跳法数是跳上n-1和跳上n-2级台阶的跳法数之和。

算法流程：

• 动态规划流程：明确 base case -> 明确「状态」-> 明确「选择」 -> 定义 dp 数组/函数的含义。

• 明确base case，即已知的初始状态：第一级台阶和没有台阶只有1种跳法

• 定义dp数组：dp[i]表示第i级台阶有多少种跳法

• 状态转移： 从第2级到第target级台阶进行状态转移

Java 版本代码如下：

public class Solution {
    public int jumpFloor(int target) {
        // dp[i]表示第i级台阶有多少种跳法
        int[] dp = new int[target + 1];
        // 状态初始化，第一级台阶和没有台阶只有1种跳法
        dp[0] = dp[1] = 1;
        // 从第2级到第target级台阶进行状态转移
        for(int i = 2; i <= target; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[target];
    }
}

也可以进行状态压缩，优化空间复杂度

public class Solution {
    public int jumpFloor(int target) {
        // dp_i_2表示dp[i-2]， dp_i_1表示dp[i-1]
        int dp_i_2 = 1, dp_i_1 = 1;
        // 从第2级到第target级台阶进行状态转移
        for(int i = 2; i <= target; i++) {
            // 修改dp[i-1]前，保存状态
            int temp = dp_i_1;
            // 相当于 dp[i] = dp[i - 1] + dp[i - 2]
            dp_i_1 += dp_i_2;
            // 更新状态
            dp_i_2 = temp;
        }
        // 返回dp[i]
        return dp_i_1;
    }
}

复杂度分析：

时间复杂度 $O(N)O(N)$：每一级台阶只遍历一次

空间复杂度 $O(1)O(1)$：进行状态压缩后，只用到两个整型变量