[LeetCode 解題紀錄] 70. Climbing Stairs

70. Climbing Stairs

https://leetcode.com/problems/climbing-stairs/

Problem:

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

Constraints:

• 1 <= n <= 45

題意

每次爬樓梯可以爬一階或是二階，找出爬到頂端總共有幾種組合方法。

例如：2 階的樓梯，有兩種方法可以爬到頂端。

1. 1 階 + 1 階
2. 2 階

問題解析

這題是在練習解 leetcode 題目的經典遞迴問題之一，也是很適合拿來練習 Dynamic Programming 的基本題目之一。這題題目給予你基本的情境，想找出從這個基本情境不段重複之後，最後的解答，因此不論要用遞迴或是動態規劃，都必須要先將這個問題的「子問題」找出來。

先列出幾回合來找規律：

n = 1, output = 1 種

1 step

n = 2, output = 2 種

1 step + 1 step
2 step

n = 3, output = 3 種

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

n = 4, output = 5 種

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

從 output 的值，我們可以觀察到規律，找出他其實就是一個費式數列：

解法

遞迴

我們可以直接用費式數列的概念，直觀地把遞迴的方法寫出來，但這種方式其實是效率不高的方法，因為它會重複計算很多次相同的子問題。

function climbStairs(n) {
    if (n <= 2) {
        return n;
    }
    return climbStairs(n - 1) + climbStairs(n - 2);
}

Dynamic programming 動態規劃

由於我們已經找出了子問題，而遞迴的方法又重複計算很多次相同的子問題，這時候使用動態規劃就是一個比較理想的做法，因為動態規劃可以將子問題的結果存起來，用查找的方式來避免重複計算。

Dynamic programming 概念複習：

演算法筆記系列 — Dynamic programming 動態規劃

我們透過使用一個陣列，來記錄所有子問題的答案，當第 N 回合需要使用前面兩回合的值，只需要直接陣列取值就好。

function climbStairs(n) {
    if (n <= 2) {
        return n;
    }
    let dp = new Array(n + 1);
    dp[1] = 1;
    dp[2] = 2;
    for (let i = 3; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

• 時間複雜度：O(n)
• 空間複雜度：O(n)

而看到這裡，其實可以發現這題當我們到了第 N 回合的時候，只需要前兩回合的值就可以了，我們其實可以只記錄前兩個值，重複利用來降低空間複雜度。

function climbStairs(n) {
    if (n <= 2) {
        return n;
    }
    let a = 1, b = 2;
    for (let i = 3; i <= n; i++) {
        let temp = a + b;
        a = b;
        b = temp;
    }
    return b;
}

• 時間複雜度：O(n)
• 空間複雜度：O(1)

更多演算法與資料結構文章：

基礎演算法與資料結構學習筆記