Leetcode 70 - Climbing Stairs

題目

Problem#

有一個 n 階的樓梯，每次可以走 1 階或 2 階，問你有幾種不同的走法

想法#

當前的走法 $i$ 可以是 $i-1$ 走 1 或是 $i-2$ 走 2 的總和，總共 0 階和 1 階的方法數是 1

(第 i 階可以是 i-1 走 1 階，或是 i-2 階走2階)

• 時間複雜度: $\mathcal{O}(1)$
• 空間複雜度: $\mathcal{O}(n)$

AC Code#

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