[LeetCode] 70. Climbing Stairs

You are climbing a staircase. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Note: Given n will be a positive integer.

Example 1:
Input: 2
Output: 2
Explanation: There are two ways to climb to the top.

1 step + 1 step
2 steps

Example 2:
Input: 3
Output: 3
Explanation: There are three ways to climb to the top.

1 step + 1 step + 1 step
1 step + 2 steps
2 steps + 1 step

Constraints:
1 <= n <= 45

爬楼梯。

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？注意：给定 n 是一个正整数。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/climbing-stairs
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

这道题有两种解法，一种是数学解法，一种是动态规划。

思路一 - 数学解法

首先是数学解法，这个题本质上是斐波那契数列。当输入为1, 2, 3, 4, 5, 6, 7, 8, 9, 10时，观察输出为1, 2, 3, 5, 8, 13, 21, 34, 55, 89。所以做法就很直观了。

复杂度

时间O(n)
空间O(1)

代码

Java实现

class Solution {
    public int climbStairs(int n) {
        // corner case
        if (n <= 1) {
            return n;
        }

        // normal case
        int zero = 1;
        int first = 1;
        int cur = 0;
        for (int i = 2; i <= n; i++) {
            cur = zero + first;
            zero = first;
            first = cur;
        }
        return cur;
    }
}

思路二 - 递归 + memorization

启发思考：寻找子问题
假设 n = 9。

我们要解决的问题是从 0 爬到 9 有多少种不同的方法。

分类讨论：

如果最后一步爬了 1 个台阶，那么我们得先爬到 8，要解决的问题缩小成：从 0 爬到 8 有多少种不同的方法。
如果最后一步爬了 2 个台阶，那么我们得先爬到 7，要解决的问题缩小成：从 0 爬到 7 有多少种不同的方法。
由于这两种情况都会把原问题变成一个和原问题相似的、规模更小的子问题，所以可以用递归解决。

注 1：从大往小思考，主要是为了方便把递归翻译成递推。从小往大思考也是可以的。

注 2：动态规划有「选或不选」和「枚举选哪个」两种基本思考方式。在做题时，可根据题目要求，选择适合题目的一种来思考。本题用到的是「枚举选哪个」。

作者：灵茶山艾府
链接：https://leetcode.cn/problems/climbing-stairs/description/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

根据上面的思路，我们发现，递归解决一个规模较大的问题，可以先看最后一步怎么解决，然后把这个问题转化为一个和原问题相似的、规模更小的子问题。所以对这道题来说，解决爬到第 n 层楼的办法，且题目定规我们一次只能爬一层或者两层，所以爬到第 n 层楼的办法就是去看爬到第 n-1 层楼和爬到第 n-2 层楼的组合数。这里我们还需要用一个 memo 数组记录中间结果。

复杂度

时间O(n)
空间O(n)

代码

Java实现

class Solution {
    int[] memo;

    public int climbStairs(int n) {
        memo = new int[n + 1];
        return helper(n);
    }

    private int helper(int i) {
        if (i <= 1) {
            return 1;
        }
        if (memo[i] != 0) {
            return memo[i];
        }
        return memo[i] = helper(i - 1) + helper(i - 2);
    }
}

思路三 - 动态规划

如果理解了递归怎么做，那么动态规划的解法就是递归解法的 1:1 翻译。

dp[i] 数组的定义是跑到第 i 层楼的时候，上楼梯的组合数是多少。几个初始值是 dp[0] = 1, dp[1] = 1。因为每次既可以爬一层楼，也可以爬两层楼，所以当你需要知道第i层楼的爬法的时候，你需要看的是我爬到 i - 2 层楼有几种爬法和我爬到 i - 1 层楼有几种爬法。所以状态转移方程就是 dp[i] = dp[i - 1] + dp[i - 2]。

复杂度

时间O(n)
空间O(n)

代码

Java实现

class Solution {
    public int climbStairs(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
}

javascript实现

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function (n) {
    if (n === 0) return 0;
    let dp = [n + 1];
    dp[0] = 1;
    dp[1] = 1;
    for (let i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
};

[LeetCode] 70. Climbing Stairs

思路一 - 数学解法

复杂度

代码

思路二 - 递归 + memorization

复杂度

代码

思路三 - 动态规划

复杂度

代码

相关题目