題目

#

leetcode 70 - Climbing Stairs (題目說明請點連結)

題目簡述

#

計算爬到第 n 階樓梯的不同方法數。

範例

#

Example 1:

Input: n = 2
Output: 2
Explanation: 有兩種方法爬到第2階：
1. 1 階 + 1 階
2. 2 階

Example 2:

Input: n = 3
Output: 3
Explanation: 有三種方法爬到第3階：
1. 1 階 + 1 階 + 1 階
2. 1 階 + 2 階
3. 2 階 + 1 階

Example 3:

Input: n = 4
Output: 5
Explanation: 有五種方法爬到第4階：
1. 1 階 + 1 階 + 1 階 + 1 階
2. 1 階 + 1 階 + 2 階
3. 1 階 + 2 階 + 1 階
4. 2 階 + 1 階 + 1 階
5. 2 階 + 2 階

解題思路

#

這題要求我們計算爬到第 n 階樓梯的不同方法數。每次可以爬 1 階或 2 階，我們需要找出所有可能的組合方式。

解法

#

1. 使用斐波那契數列的概念來解決
2. 爬到第 n 階的方法數等於爬到第 n-1 階的方法數加上爬到第 n-2 階的方法數
3. 使用三個變數來優化空間複雜度：step1、step2、curr

步驟

#

• 如果 n <= 3，直接返回 n（因為這些情況很容易計算）
• 初始化 step1 = 1（爬到第1階的方法數）和 step2 = 2（爬到第2階的方法數）
• 從第3階開始，使用迴圈計算每一階的方法數：
  • curr = step1 + step2
  • 更新 step1 = step2，step2 = curr
• 最終返回 curr（爬到第n階的方法數）

數學原理

#

這題本質上是斐波那契數列問題：

• f(n) = f(n-1) + f(n-2)
• 其中 f(1) = 1，f(2) = 2

例子說明

#

n = 4

1. 初始化：

   • step1 = 1（爬到第1階的方法數）
   • step2 = 2（爬到第2階的方法數）

2. 計算第3階：

   • curr = step1 + step2 = 1 + 2 = 3
   • 更新：step1 = 2，step2 = 3

3. 計算第4階：

   • curr = step1 + step2 = 2 + 3 = 5
   • 更新：step1 = 3，step2 = 5

4. 最終結果：

   • 爬到第4階有5種方法

完整程式碼

#

class Solution {
    public int climbStairs(int n) {
        // 如果n小於等於3，直接返回n（這些情況很容易計算）
        if(n <= 3) return n;

        // 初始化前兩階的方法數
        int step1 = 1;  // 爬到第1階的方法數
        int step2 = 2;  // 爬到第2階的方法數
        int curr = 0;   // 當前階數的方法數
        
        // 從第3階開始，逐階計算到第n階
        for(int i = 3; i <= n; i++){
            // 當前階數的方法數等於前一階加前兩階的方法數
            curr = step1 + step2;
            // 更新變數，為下一輪計算做準備
            step1 = step2;  // step1變成前一階的方法數
            step2 = curr;   // step2變成當前階的方法數
        }

        // 返回爬到第n階的方法數
        return curr;
    }
}

時間複雜度

#

• 時間複雜度：O(n)，需要遍歷從第3階到第n階
• 空間複雜度：O(1)，只使用了常數個變數來存儲狀態

其他解法

#

遞迴法（不推薦，會超時）

#

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

陣列法（空間複雜度較高）

#

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