問題70：假設你正在爬樓梯。需要n階你才能到達樓頂。每次你可以爬1或2個臺階。你有多少種不同的方法可以爬到樓頂呢？

動態(tài)規(guī)劃，無法打印路徑，不知道具體方案什么樣，較簡單地解決統(tǒng)計數(shù)量的問題；
DFS：可以把方案打印出來。

要想爬到第n級臺階，只有兩種情況：

• 從第n-1級臺階，向上爬一步；
• 從第n-2級臺階，向上爬兩步。

因此，狀態(tài)轉移方程為：

完整代碼：

class Solution:
    def climbStairs(self, n: int) -> int:
        if n == 1 or n == 2:
            return n
        dp = [None for _ in range(n+1)]
        dp[1] = 1
        dp[2] = 2
        i = 3
        while i <= n:
            dp[i] = dp[i-1] + dp[i-2]
            i += 1
        return dp[n]

運行結果：