LeetCode 双刀流：70. Climbing Stairs

70. Climbing Stairs

这是一个动态规划的经典题目「爬楼梯」，这个题目根据规则利用「递回」其实蛮直觉的。只是递回在这个题目中会存在一些效能与重复计算的问题，所以我们试图从这个例子中观察递回的问题，并且引入一种称为「动态规划（Dynamic Programming，DP）」的方法。

先看一下题目描述

You are climbing a staircase. It takes n steps to reach the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

再搭配范例理解题目

• Example 1:

Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

• Example 2:

Input: n = 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

本题需要求的是当走到 n 阶楼梯时有多少种可能，每一次可以移动一步或两步。

开始实作

在理解完题目与条件之後，那我们下一步就开始「#初探直觉解」并且一起尝试「#刻意优化」的过程：

方法 ①：递回法

根据观察之後，我们可以会发现「爬第 n 阶楼梯的方法数」等於「爬上 n−1 阶楼梯的方法数量」 + 「爬上 n−2 阶楼梯的方法数量」。根据这样的观察与规则之後，很容易就会想到使用递回的解法，可以写出以下的写法：

f(n) = f(n-1) + f(n-2)

用 Python 实作一次

class Solution:
    def climbStairs(self, n: int) -> int:
        W = [0, 1, 2]
        if len(W) < n:
            W[n] = climbStairs(n - 2) + climbStairs(n - 1);

        return W[n];

也可以用 JavaScript 复刻一次

var climbStairs = function(n) {
    let W = [0, 1, 2];
    if (W.length < n){
        W[n] = climbStairs(n - 2) + climbStairs(n - 1);
    }

    return W[n];
};

方法 ②：动态规划法

方法一采用递回的规则如下：

f(n) = f(n-1) + f(n-2)

这个题目使用递回会存在一个问题，就是每次计算 f(n) 之後，会去递回计算 f(n-1) + f(n-2)。相同的概念在计算 f(n-1) 会去计算 f(n-2) + f(n-3)、f(n-2) 会去计算 f(n-3) + f(n-4)，以这个例子来看，f(n-3) 会同时在 f(n-1) 和 f(n-2) 重复计算。这样一来，当 n 很大的时候就会有更多的值会再递回过程中重复计算。

因此这里想法是能不能将刚刚的 f(n-3) 给记录下来，而不用每一个递回过程都重复计算。所以我们想到的是将结果存在一个变数当中（而非每次都计算），将递回的过程暂存到一个变数中，如下：

dp[i] = dp[i - 1] + dp[i - 2]

用 Python 实作一次

class Solution:
    def climbStairs(self, n: int) -> int:
        W = [0, 1, 2]
        for i in range(3, n):
            W[i] = W[i - 2] + W[i - 1]
        return W[n]

也可以用 JavaScript 复刻一次

var climbStairs = function(n) {
    var W = [0, 1, 2];
    for (var i = 3; i <= n; i++) {
        W[i] = W[i - 2] + W[i - 1];
    }

    return W[n];
};

反思沉淀

本题的规则是「爬第 n 阶楼梯的方法数」等於「爬上 n−1 阶楼梯的方法数量」 + 「爬上 n−2 阶楼梯的方法数量」，你有没有觉得这个概念很熟悉？这其实一种称为「费氏数列」或「斐波那契数列」（Fibonacci）的东西，每一个数回等於前两个数的总和，这是资工系或是演算法中相当经典的问题。本题可以算是从费氏数列延伸出来的应用，因为相当生活化，并且可以同时使用到「递回」与「动态规划」两种解法。

举一反三看看相似题

最後可以从题目提供的相似题看一下有哪些类似的题目，适合作为你下一个尝试的练习：

• 746. Min Cost Climbing Stairs
• 509. Fibonacci Number
• 1137. N-th Tribonacci Number

嗨，大家好！我是维元，一名擅长网站开发与资料科学的双栖工程师，斜杠於程序社群【JSDC】核心成员及【资料科学家的工作日常】粉专经营。目前在 ALPHACamp 担任资料工程师，同时也在中华电信、工研院与多所学校等单位持续开课。拥有多次大型技术会议讲者与竞赛获奖经验，持续在不同的平台发表对 #资料科学、 #网页开发 或 #软件职涯 相关的分享，邀请你加入 订阅 接收最新资讯。