A

ASCE1885

V1

2022/07/28阅读:7主题:默认主题

【萌新解题】爬楼梯

关于我:微信公众号:面试官问,原创高质量面试题,始于面试题,但不止于面试题。【萌新解题】系列文章试图从新人的角度去看待和解决力扣题目,本题是力扣第 70 题 爬楼梯:https://leetcode.cn/problems/climbing-stairs/。

这道题目虽然难度是简单,但如果你思维没有转过弯来,不能得出正确的解题公式,其实并不简单。题目要求爬到楼顶(有n个阶梯)有多少种方法,我们通过数学归纳法,先定义 f(n) 表示爬了n个阶梯有 f(n) 种方法,而题目的限定是你每次只能爬 1 个或者 2 个台阶,那么假设你已经爬了 n 阶楼梯,有 f(n) 种方法,那么到达这个状态,有两种可能:

  1. 你在 n-1 阶楼梯通过爬 1 个台阶到达 n 阶楼梯的位置,而你到达 n-1 阶楼梯时有 f(n-1) 种方法
  2. 你在 n-2 阶楼梯通过爬 2 个台阶到达 n 阶楼梯的位置,而你到达 n-2 阶楼梯时有 f(n-2) 种方法

因此,你到达 n 阶楼梯时,有 f(n) = f(n-1) + f(n-2) 种方法。

到这里,我们已经得出计算公式,其实就是斐波那契数列,那么我们同样可以使用递归和动态规划的解法,我们先试试递归解法:

class Solution {
    public int climbStairs(int n) {
        if (n == 1 || n == 2) {
            return n;
        }
        return climbStairs(n-1) + climbStairs(n-2);
    }
}

提交代码运行得到如下结果,当 n=45 时,代码运行超出时间限制:

image.png
image.png

既然单纯的递归执行超时,我们试下增加备忘录,避免重复子问题,看是否能够正常执行,代码如下:

class Solution {
    public int climbStairs(int n) {
        // 题目中,n 大于等于 1
        if (n == 1) {
            return 1;
        }

        // 初始化备忘录数组,数组大小是 n+1,因为数组是从1开始,而题目要求的是climbStairs(n)的值
        int[] memo = new int[n+1];
    
        return helper(memo, n);
    }

    /**
     * 辅助函数
     */

    private int helper(int[] memo, int n) {
        // base case
        if (n == 1 || n == 2) {
            return n;
        }

        // 备忘录模式,避免重复计算
        if (memo[n] != 0) {
            return memo[n];
        }

        // 递归调用,并保存返回值到备忘录数组中
        memo[n] = helper(memo, n-1) + helper(memo, n-2);
        return memo[n];
    }
}

执行结果通过,如下所示:

image.png
image.png

类似【萌新解题】斐波那契数列 一文,我们也可以使用动态规划来解决爬楼梯问题,本文我们使用的动态规划解题六步骤如下:

  1. 确定 dp 数组以及下标的含义(dp数组可能是一维数组、二维数组等)
  2. 确定递推公式
  3. dp 数组如何初始化
  4. 确定 dp 数组的遍历顺序,可能是正向遍历、反向遍历、斜向遍历等
  5. 举例推导dp数组,通过把dp数组打印出来,并和自己人脑计算的结果对比,用于调试使用
  6. 思考是否可以状态压缩,进一步提升空间效率

套用到爬楼梯这个场景,如下所示:

  1. 确定 dp 数组以及下标的含义:dp[i] 表示爬了n个阶梯有 dp[i] 种方法
  2. 确定递推公式:通过文章开头的分析,我们得到递推公式为:dp[n] = dp[n-1] + dp[n-2]
  3. dp 数组如何初始化:题目中已经给出来了,即 dp[0]=1; dp[1]=1;
  4. 确定 dp 数组的遍历顺序:当想得到 dp[n] 的值是,我们首先得知道 dp[n-1] 和 dp[n-2] 的值,因此,我们需要从小到大遍历数组
  5. 举例推导dp数组:需要调试时使用即可
  6. 思考是否可以状态压缩:如果现在想不清楚,可以等我们写完上面代码后可以再考虑

最终得到的动态规划解法代码如下:

class Solution {
    public int climbStairs(int n) {
        // 初始化dp数组
        int[] dp = new int[n+1];
        dp[0] = 1;
        dp[1] = 1;
        
        // dp数组从小到大遍历
        for (int i=2; i<=n; ++i) {
            dp[i] = dp[i-1] + dp[i-2];
        }

        return dp[n];
    }
}

最后,再使用状态压缩,得到简化后的代码如下:

class Solution {
    public int climbStairs(int n) {

        // 确定dp数组的初始化状态
        int prev = 1;
        int current = 1;
        int sum = 0;
        
        // 循环迭代,dp数组遍历顺序是从小到大
        for (int i=2; i<=n; ++i) {
            sum = prev + current;
            prev = current;
            current = sum;
        }
        
        return current;
    }
}

分类:

后端

标签:

后端

作者介绍

A
ASCE1885
V1