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?

Understand

總共有n階，每次只能爬1階或爬2階，要找出共有幾種排列組合可以爬到第n階

Happy Case

input	output	說明
n = 1	1	[1]
n = 2	2	[1,1]或[2]
n = 3	3	[1,1,1]或[2,1]或[1,2]

Edge Case

input	output	說明
n = 0	1	不動也是一種方法

Match

題目要考得是動態規劃

爬到第n階總共可以有幾種方法，使用動態規劃的思路(大問題是由多個小問題的答案推導出來的)，所以

爬到第n階的組合數量 = 爬到第n-1階的組合數量 + 爬到第n-2階的組合數量

Plan

採用Buttom-up，從小問題遞迴推向大問題

確定爬到第一階與不爬的方法數量: dp[0] = 1、dp[1] = 1
從第二階梯開始堆疊到第n階梯，每次令dp[n] = dp[i-1] + dp[i-2]

🌟 採用【變數滾動更新】的方式，不用陣列儲存每個dp[i]的值，如此可降低空間複雜度

Implement

def climbStairs(n:int) -> int:
    # 先解決Edge Case
    if n <= 1:
        return 1

    prev = 1
    prev2 = 1

    for i in range(2, n+1, 1):
        curr = prev + prev2

        # 更新變數
        prev2 = prev
        prev = curr

    return prev

Review

input	output
0	1
1	1
2	2
3	3
5	8

Evaluate

複雜度	值	說明
時間複雜度	O(n)	只run一遍2~n的所有值
空間複雜度	O(1)	只使用兩個變數

【題目】爬樓梯