題目連結: 70. Climbing Stairs

題目描述:總共 n 階樓梯，每次可以爬 1 階或 2 階，問有多少種不同的方法可以爬到頂部？

Example 1:
Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.

Example 2:
Input: n = 3
Output: 3
Explanation: There are three ways to climb to the top.

Python

解題思路:
我要想到達第 n 階，最後一步是怎麼來的？

情況一：從第 n-1 階爬 1 階上來。

情況二：從第 n-2 階爬 2 階上來。

所以，到達第 n 階的總方法數，就等於到達第 n-1 階的方法數+ 到達第 n-2 階的方法數。

因此，有一個遞迴公式:ways(n) = ways(n-1) + ways(n-2)。

這個遞迴會產生大量的「重疊子問題」。例如計算 ways(5) 時，會計算 ways(4) 和 ways(3)；而計算 ways(4)

時，又會重新計算一次 ways(3)。當 n 很大時，這種重複計算會導致效能極差，最終超時。

DP的方法就有效的解這題，創建一個 dp 陣列，dp[i] 的意義是：爬到第 i 階總共有多少種方法。

dp[i] 的值取決於它前兩階的方法數之和。

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

舉例來說，
dp[0]：爬到第 0 階，可以理解為「還沒開始爬」，本身就是一種狀態，所以 dp[0] = 1。

dp[1]：爬到第 1 階，只有一種方法（爬 1 階），所以 dp[1] = 1。

class Solution:
    def climbStairs(self, n: int) -> int:
        dp0 = 1
        dp1 = 1
        for i in range(2,n+1):
            curr = dp0 + dp1
            dp1 = dp0
            dp0 = curr
        if n<=1:
            return 1
        return dp0

演算法分析:

• for i in range(2, n + 1):我們從第 2 階開始計算，因為 0 和 1 階已經是已知。
• curr = dp0 + dp1相等於 dp[i] = dp[i-1] + dp[i-2]。
• 在計算完第 i 階的方法數後，我們將 dp1 的值「降級」給 dp2，並將 curr 的值賦給 dp1，讓它們滾動向前，為計算第 i+1 階做準備。
• 迴圈運行到最後一次（i = n）時，dp1 被賦予了 dp[n] 的值。迴圈結束後，直接返回 dp0 就是最終答案。

複雜度分析:

• 時間複雜度為: O(n)(我們只需要一個 for 迴圈，從 2 遍歷到 n。)。
• 空間複雜度： O(1)(我們只使用了 dp0, dp1, curr 等固定數量的變數。)。

有問題可以底下留言!
下回見!!!