題目出處
難度
easy
題目分類
Math, Dynamic Programming, Memoization
2026-07-21 二刷
個人範例程式碼 - 二刷 (2026/07/21)
class Solution:
def climbStairs(self, n: int) -> int:
curr, prev = 1, 0
for _ in range(n):
curr, prev = curr+prev, curr
return curr
算法說明
DP題目, 不過其實只有需要分析前一個與前兩個, 可以簡化為使用兩個變數動態存值
Time Complexity
O(n)
Space Complexity
O(1)
2022-05-04 一刷
個人範例程式碼 - 一刷 (2022/05/04)
class Solution:
def climbStairs(self, n: int) -> int:
# dp[i] = dp[i-1] + dp[i-2]
if n == 0:
return 0
dp = []
for i in range(n):
if i == 0:
dp.append(1)
elif i == 1:
dp.append(2)
else:
dp.append(dp[-1] + dp[-2])
return dp[-1]
最近在練習程式碼本身就可以自解釋的 Coding style，可以嘗試直接閱讀程式碼理解
算法說明
利用 dp[i] = dp[i-1] + dp[i-2]
input handling
處理開頭 i = 0 的情況，return 0
i = 1, return 1
i = 2, return 2
Boundary conditions
控制 for-loop 的範圍