動態規劃的維度

我們可以透過表格的維度、以及轉移所需要考慮的時間，將動態規劃的演算法簡單作一些分類。比方說解決 LCS 的演算法，它是個二維表格、常數時間轉移，所以我們可以粗略地說它是個 2D/0D 的動態規劃。

今天我們來看一些轉移沒那麼常數的例子！

切木板問題

題目敘述是這樣的：你有一條木板。你想要把這條木板由左到右切成長度分別是 a[0], a[1], ..., a[n-1] 這麼多段（這些段落由左而右的順序必須是固定的）。切木板是需要成本的：對於一條長度為 L 的木板，瞄準木板上任何一個位置 x，精準地切下去得到長度為 x 與 L-x 的兩片較短的木板，所需要的花費剛好是 $L 元。請問成功把這些木板切出來需要多少總成本呢？

解題思考

我們用 dp(l, r) 代表目前的木板應該要被切出 a[l]...a[r] 這些長度，所需的最小花費。那麼由於總長度已經被固定了，下手的第一刀無論怎麼切都會出現 a[l]+...+a[r] 的花費。因此我們可以考慮第一刀的位置，假設切在 a[l]+..+a[m] 的位置，那麼左半邊的子問題就會是 dp(l, m)、右半邊的子問題就會是 dp(m+1, r)。因此我們可以把遞迴關係寫成：

計算一個狀態需要的時間是 O(r-l) = O(n)，而總共有 O(n^2) 個可能的 (l, r) 值。因此這是一個 2D/1D 的問題，時間複雜度粗估是 O(n^3)。

最佳二元搜尋樹問題

我們知道二元搜尋樹的定義是：將 n 筆可排序資料掛在一棵二元樹上，然後滿足它的中序走訪必須是由小到大排列的。當我們要搜尋某一筆特定資料的時候，就可以從樹根開始每一次進行比較：如果欲搜尋資料等於樹根之鍵值，那我們就找到它了。如果不相等，那根據大小關係我們可以直接前往左子樹或右子樹進行搜索。

如果每一筆資料的搜尋頻率都相同的話，顯然我們使用一棵平衡二元搜尋樹就可以解決問題——對於每一次詢問，期望搜尋時間大約都是 Θ(log n)。如果今天已知每一筆資料被搜尋的機率，是否能夠找出最佳的二元搜尋樹，使得期望搜尋時間最小呢？

解題思考

跟第二天的二元搜尋樹的計數問題類似，我們可以從根節點來下手。決定了跟節點以後，剩下的資料就會被分成較小的部分與較大的部分。而今天搜尋所花費的期望時間，便是「進入這棵子樹的機率」，加上左子樹和右子樹的期望搜索時間——這個形式便與上面切木板問題相當類似了。

遞迴關係可以寫成：

雖然解讀方法稍有不同，但是兩題相當類似唷！

延伸思考

• 霍夫曼編碼(Huffman Codes)也是試圖找出期望長度最短的編碼方式演算法。本題與霍夫曼編碼有什麼不同之處呢？

今天的最後，我們用一個最佳二元搜尋樹+切木板問題的加強版問題來總結吧！

Exercise 16: Leetcode 1000 - Minimum Cost to Merge Stones

題目連結

https://leetcode.com/problems/minimum-cost-to-merge-stones/

題目敘述

你有一個序列的 N 個石頭堆排成一排，第 i 堆有 stone[i] 顆石頭。每一次操作，你可以挑選連續的 K 堆石頭，然後把它們合併成一堆。當然，這個動作是有花費的，合併連續的 K 堆石頭需要花費恰好等於合併的總石頭數量。

請問把所有石頭合併成一堆最小總花費為何？

解題思考

這題根本就是切木板的反過來版本啊（把木板黏回來）而且還是加強版！一次可以黏 K 塊木板！於是我們可以定義 dp(i, j) 是指把所有 stone[i..j] 的石頭堆全部合併成一堆的最小總花費（如果無法做到的話就是無窮大 float("inf")）顯然這次不能只切兩份，而是要決定要怎麼把它切成 K 個部分，使得總花費最小。

這個部分變成另一個 DP 問題：給你一個序列 stone[l, l+1, ..., r]，要分成 K 個部分，如果某一部分恰好只有一個值，那麼花費為 0，否則花費是將該部分所有石頭合併成一堆的最小花費。因此，狀態的轉移上面就變成了一個 的動態規劃：我們用 dp2(x, y) 表示將 stone[l, ..., x-1] 拆成 y 部分所需要的最小花費。這個問題的轉移就會是將包含 x 的最後一段拉出來，所以寫成

整體的時間複雜度是 ...是個 2D/3D 動態規劃呢。

參考程式碼 (Python3)

class Solution:
    def mergeStones(self, stones: List[int], K: int) -> int:
        n = len(stones)
        dp = [[float("inf")] * n for _ in range(n)]

        # 內層的動態規劃
        def cutIntoKSegments(l: int, r: int) -> int:
            # 這邊是 dp2 表格
            table = [[float("inf")] * (K+1) for _ in range(r-l+2)]
            table[0][0] = 0
            for i in range(l, r+1):
                for j in range(1, K+1):
                    table[i+1-l][j] = min([table[k-l][j-1] + dp[k][i] \
                                           for k in range(l, i+1)])
            return table[r+1-l][K]

        # 外層的動態規劃
        for j in range(n):
            for i in range(j, -1, -1):
                # 不可能把 [i..j] 這段縮成一個點的情形：直接跳過。
                if (j - i) % (K - 1) != 0:
                    continue
                if i == j:
                    dp[i][j] = 0
                    continue
                dp[i][j] = cutIntoKSegments(i, j) + sum(stones[i:j+1])
        answer = dp[0][n-1] if math.isinf(dp[0][n-1]) == False else -1
        return answer

後記

今天講的幾個問題其實都還可以加速唷，這個我們之後有機會慢慢談～