描述

思路

  • 递归
  • 动态规划

知识点:递归,动态规划

难度:⭐⭐


题解

图解:

image-20211013112125530

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

方法一:递推

解题思路:

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

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

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

img

算法流程:
  • 定义递归函数功能:返回跳到第 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(n2)O(n^2),没有消除重叠子问题,每个节点会递归两次

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

方法二:记忆化搜索

image-20211013114247230

算法流程:
  • 通过一个长度为 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):进行状态压缩后,只用到两个整型变量