目錄

在上一篇，我們簡介了動態規劃的基本概念與解題時應用的兩種策略。

今天開始，我們會從Easy難度入門，介紹各種不同的動態規劃題型與解題時的訣竅。

若各位讀者有時間，務必自己也思考、動手實作看看這些例題，實作才是掌握知識最快的捷徑！

🟩爬樓梯

本題取自Leetcode 70. Climbing Stairs。

題目

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?

Constraints:
1 <= n <= 45

Example 1:

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

Example 2:

Input: n = 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

分析

分治法

先確認題目的規則：從第0階出發，每次能往上走1或者2階。母問題詢問：走到第n階，有幾種走法？

  • 如果樓梯只有1階，那麼就只有0→1這1種走法。

  • 如果樓梯有2階，那麼可以從0階直接走到2階，也可以從0→1→2階，也就是2種走法。

  • 如果樓梯有3階呢？一共有3種走法：

0 → 1 → 2 → 3
0 → 1 →     3
0 →     2 → 3

可以發現，窮舉法能夠應付較小的問題，然而隨著階數越多，走法也會越來越多樣化，因此，需要一個不同的觀點(分治：把複雜的問題變簡單)

我們試著關注：「一步」能夠走到3階，可以從哪裡走？

因為一步只能走1或者2階，因此，要在一步內走到3階，只能從1階或者2階出發。

... → 1 →     3 
...     → 2 → 3

要抵達3階，我們只能：

  • 透過任何一種方式走到1階之後，走一步到3階

或者

  • 透過任何一種方式走到2階之後，走一步到3階

且這兩種走法互斥，不會重複計算。

換言之：

  • 走到3階的路徑總數 = 走到1階的路徑總數 + 走到2階的路徑總數

將這個觀念推廣至k階，就得到：

  • 走到k階的路徑總數 = 走到k-1階的路徑總數 + 走到k-2階的路徑總數
  • 其中 k >= 2 (走到0階的路徑數 = 起點 = 1種)

設計狀態、找出轉移式與最小問題

我們定義狀態ways(k)：從0階出發、走到k階的路徑總數

根據分治法得到的結論，轉移式可以寫作：

ways(k) = ways(k-1) + ways(k-2) (對所有k>=2)

最小問題(最簡狀態)分別是

ways(0) = 0 (起點0階)

ways(1) = 1 (從0階走到1階，只有1種走法)

而母問題所求走到n階的路徑總數，也就是在求ways(n)

實作

Top-Down DP

class Solution:
    # 記錄計算過的狀態
    def __init__(self):         
        self.cache = {}
    # 遞迴函式
    def climbStairs(self, n: int) -> int:
        # 如果已經計算過，就直接回傳記錄好的子問題答案
        if n in self.cache:
            return self.cache[n]
        # 最小子問題(起點or走到1階)
        if n <= 1:
            return 1
        # 遞迴關係式(狀態轉移式)
        # 回傳狀態之前，先記錄在self.cache。
        self.cache[n] = self.climbStairs(n-1) + self.climbStairs(n-2)
        # 回傳子問題的答案
        return self.cache[n]

Leetcode在帶入測資時，實際上是先實例化Solution，再呼叫實例的求解方法，以本題為例，虛擬碼類似這樣：

解法 = Solution()

for 測資i,正解 in 測資s:

    使用者解答 = 解法.climbStairs(測資i)
    assert(使用者解答 == 正解)

因此，我們需將記錄用的陣列寫成Solution的屬性，來記錄climbStairs計算過的答案。

如果懶得手刻快取，也可以使用functools函式庫的快取模組cache或者lru_cache。

from functools import cache

class Solution:
    @cache 
    # 遞迴函式
    def climbStairs(self, n: int) -> int:
        # 最小子問題
        if n <= 1: return 1
        # 遞迴關係式
        return self.climbStairs(n-1) + self.climbStairs(n-2)

Bottom-Up DP

class Solution:
    def climbStairs(self, n: int) -> int:
        # 最小子問題(起點or走到1階)
        dp = [1,1] # 記錄答案用的list，index=i代表走到第i階的走法數
        # 計算順序：從小到大
        for i in range(2,n+1):
            # 狀態轉移式
            # 計算完，將子問題的答案記錄進dp陣列
            dp.append(dp[i-1]+dp[i-2])
        # 回傳母問題(i=n)的答案
        return dp[n]

如果要對空間作優化，使用滾動式dp

計算順序不變，但只記錄最後兩階的走法數

class Solution:
    def climbStairs(self, n: int) -> int:
        # 最小子問題(走到1階)
        prev, curr = 1, 1 # 前一階、這一階
        # 計算順序：從小到大(i=2 → i=n)
        for i in range(2,n+1):
            prev, curr = (curr, prev + curr)
        # 回傳母問題(i=n)的答案
        return curr

複雜度分析

時間複雜度

本題為1-D DP，狀態數 = O(n)

每個狀態的計算複雜度為 O(1)

時間複雜度 = 狀態數 x 計算複雜度 = O(n) x O(1) = O(n)

空間複雜度

需記錄每個狀態的答案，因此空間複雜度為O(n)

若採用rolling Bottom-Up DP，少一維度，因此空間複雜度為O(1)

🟩三波納契數列

本題取自 Leetcode 1137. N-th Tribonacci Number

題目

The Tribonacci sequence Tn is defined as follows:

T0 = 0, T1 = 1, T2 = 1, and Tn+3 = Tn + Tn+1 + Tn+2 for n >= 0.

Given n, return the value of Tn.

Example 1:

Input: n = 4
Output: 4
Explanation:
T_3 = 0 + 1 + 1 = 2
T_4 = 1 + 1 + 2 = 4

Example 2:

Input: n = 25
Output: 1389537

Constraints:

0 <= n <= 37
The answer is guaranteed to fit within a 32-bit integer, ie. answer <= 2^31 - 1.

分析

本題定義所謂的三波納契數列

其實就只是把原本費波納契數列的前兩項之和，改為前三項之和。

因此，和原本的費波納契數列一樣，轉移式就是數列的規則本身：

t(n) = t(n-1) + t(n-2) + t(n-3) ，對所有n>=3。

實作

Top-Down DP

class Solution:
    @cache
    def tribonacci(self, n: int) -> int:
        if n == 0: return 0
        if n == 1 or n== 2: return 1
        return (
            self.tribonacci(n-1) + 
            self.tribonacci(n-2) + 
            self.tribonacci(n-3)
        )

手刻快取的做法可以參考第一題。

Bottom-up DP

class Solution:
    def tribonacci(self, n: int) -> int:
        dp = [0,1,1]
        for i in range(3, n+1):
            dp.append(dp[i-1] + dp[i-2] + dp[i-3])
        return dp[n]

滾動dp來節省儲存空間的做法可以參考第一題。

複雜度分析

和原版的費氏數列相同，時間複雜度、空間複雜度均為O(n)。

(若採用滾動Bottom-Up DP，則空間複雜度降為O(1)

🟩最小成本爬樓梯

本題取自 Leetcode 746. Min Cost Climbing Stairs

題目

You are given an integer array cost where cost[i] is the cost of ith step on a staircase. Once you pay the cost, you can either climb one or two steps.

You can either start from the step with index 0, or the step with index 1.

Return the minimum cost to reach the top of the floor.

Example 1:

Input: cost = [10,15,20]
Output: 15
Explanation: You will start at index 1.
- Pay 15 and climb two steps to reach the top.
The total cost is 15.


Example 2:

Input: cost = [1,100,1,1,1,100,1,1,100,1]
Output: 6
Explanation: You will start at index 0.
- Pay 1 and climb two steps to reach index 2.
- Pay 1 and climb two steps to reach index 4.
- Pay 1 and climb two steps to reach index 6.
- Pay 1 and climb one step to reach index 7.
- Pay 1 and climb two steps to reach index 9.
- Pay 1 and climb one step to reach the top.
The total cost is 6.
 

Constraints:

2 <= cost.length <= 1000
0 <= cost[i] <= 999

分析

題目和前面出現過的爬樓梯(Leetcode70)類似，不過前一題求的是「所有走法總數」，本題則是加入「過路費」的概念，要求出「所有走法之中，過路費總和最低的」。

每一階樓梯都必須要付出cost[i]，才能繼續往上走1或者2階，直到走到階梯頂端(可以視為cost陣列最後多新增一格、且成本為0)

分治法

  • 如果只有一階length(cost)==1，則最小的花費就是那一階的費用cost[0]

  • 如果有兩階length(cost)==1，則最小的花費是什麼呢？

    因為題目規定「可以從0階或者1階出發」，所以最小的花費就是這兩階的花費之中較小的。 min(cost[0], cost[1])

  • 如果有三階呢？(命其為0、1、2階)

    • 因為「一步」能走1~2階，因此，可以從第1或者第2階走到頂端(3階) 
      ?... → 1 →     (3) # 最小花費為：cost[1]
?...     → 2 → (3) # 最小花費為：cost[2] + 「從0走到2為止的最小花費」
    • 然後再取兩種走法其中花費較小的。

因此，本題可以分治為較小的子問題：「走到第k階之前，所需要的最小費用」

  • k = 0 或 k = 1時，費用為0(出發點)
  • 剩下的階數，有兩種走法，並取其中較小的：
    • 先走到k-1階，再花費cost[k-1]，走到k階
    • 先走到k-2階，再花費cost[k-2]，走到k階
  • 題目所求，為走到頂端(k = len(cost))的最小費用

設計狀態、找出轉移式與最小問題

定義狀態　minCost(k)：從0階出發走至k階以前所需要的最小花費

根據分治法所得到的結論，轉移式可以寫作：

minCost(k) = min( minCost(k-1) + cost[k-1] , minCost(k-2) + cost[k-2] )

最小問題：minCost(0) = 0、minCost(1) = 0(因為不需要「走到」起點)

題目所求為：minCost(length(cost))

實作

Top-Down DP

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        @cache
        def minCost(i):
            if i<=1: return 0
            return min(
                minCost(i-1) + cost[i-1] ,
                minCost(i-2) + cost[i-2]
            )
        return minCost(len(cost))

手刻快取的做法可以參考第一題。

Bottom-Up DP

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        dp = [0,0]
        for i in range(2, len(cost)+1):
            dp.append(min(
                dp[i-1] + cost[i-1],
                dp[i-2] + cost[i-2]
            ))
        return dp[-1]

滾動dp來節省儲存空間的做法可以參考第一題。

複雜度分析

時間複雜度

本題為1-D DP，狀態數 = O(n)

無論測資大小，轉移式固定為兩個加法再取其中較小(min)，因此每個狀態的計算複雜度=O(1)

時間複雜度 = 狀態數 x 計算複雜度 = O(n) x O(1) = O(n)

空間複雜度

需記錄每個狀態的答案，因此空間複雜度為O(n)

若採用rolling Bottom-Up DP，少一維度，空間複雜度為O(1)

結語

作為1-D DP中較簡單的費氏數列類型，轉移式並不會太難推得，而一旦推出正確的轉移式，剩下只需要注意邊界條件(最小子問題、母問題分別對應哪個狀態？)就水到渠成！

我特別挑選兩個「爬樓梯」問題，是希望能讓讀者順便比較、發現：原來「求路徑總數」的問題和「求所有路徑中○○的最大/最小值」這兩類問題，其轉移式的推導過程是幾乎相同的，甚至最終的型態也相差不遠(前者是計數並相加，後者則是對某個權重因子求極值)。

在未來遇到相對複雜的問題的時候，這種「似曾相識」的感覺也能幫助我們觸類旁通、找出正確的轉移式。

以上為Day3的內容！感謝你的閱讀，如果有不同的想法或心得，歡迎留言一同討論！

本系列文也同步登載在我的個人部落格，記錄我的學習筆記與生活點滴，歡迎來逛逛。

明天我們會繼續探索費氏數列類型的問題。