Climbing Stairs

/**
 * 計算爬樓梯的所有可能方法數
 *
 * 原理：每一階的方法數等於前兩階方法數的總和
 * - 從 n-1 階爬 1 步到達 n 階
 * - 從 n-2 階爬 2 步到達 n 階
 */
export function climbStairs(totalStairs: number): number {
  // 處理基礎案例
  if (totalStairs <= 2) {
    return totalStairs;
  }

  // 初始狀態
  let [twoStepsBefore, oneStepBefore] = [1, 2];

  // 從第 3 階開始計算
  Array.from({ length: totalStairs - 2 }).forEach(() => {
    [twoStepsBefore, oneStepBefore] = [
      oneStepBefore,
      twoStepsBefore + oneStepBefore,
    ];
  });

  return oneStepBefore;
}

import { describe, expect, it } from 'vitest';
import { climbStairs } from './solution';

describe('climbing Stairs', () => {
  it('應該正確處理基礎案例', () => {
    // n <= 2 的情況
    expect(climbStairs(1)).toBe(1);
    expect(climbStairs(2)).toBe(2);
  });

  it('應該正確計算一般案例', () => {
    // n > 2 的情況
    expect(climbStairs(3)).toBe(3);
    expect(climbStairs(4)).toBe(5);
    expect(climbStairs(5)).toBe(8);
  });

  it('應該能處理較大的數字', () => {
    // 測試較大的階數
    expect(climbStairs(6)).toBe(13);
    expect(climbStairs(7)).toBe(21);
  });
});

動態規劃方法

這個問題可以用動態規劃來解決，實質上是斐波那契數列的應用。

狀態轉移方程

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

空間優化

不需要儲存所有的狀態，只需要前兩個狀態即可：

1. 初始化：第 1 階有 1 種方法，第 2 階有 2 種方法
2. 狀態轉移：當前階數的方法數 = 前一階方法數 + 前兩階方法數
3. 滾動陣列：使用兩個變數來節省空間

複雜度分析

• 時間複雜度: O(n) - 需要計算到第 n 階
• 空間複雜度: O(1) - 只使用兩個變數儲存狀態

斐波那契數列對應表