🧮 2-D DP

二維狀態與網格上的動態規劃。

32 題

📖 分類導讀

二維動態規劃將狀態擴展到兩個維度，常見於字串比較、網格路徑、區間 DP 等問題。

Notes:

  • 常見狀態定義：dp[i][j] 代表「前 i 個元素和前 j 個元素的最優解」
  • 網格型 DP：狀態通常是座標 (i, j)
  • 字串型 DP：狀態通常是兩個字串的索引 (i, j)

兩大家族

  • 網格型：dp[i][j] 是「走到座標 (i, j)」的最優解，轉移多半來自上方與左方（dp[i-1][j]、dp[i][j-1]）。最小路徑和、不同路徑數屬此類。
  • 雙序列型：dp[i][j] 是「第一個字串前 i 個、第二個字串前 j 個」的最優解。最長公共子序列、編輯距離屬此類。
// 編輯距離：把 word1 變成 word2 的最少操作數
fun minDistance(word1: String, word2: String): Int {
    val m = word1.length; val n = word2.length
    val dp = Array(m + 1) { IntArray(n + 1) }
    for (i in 0..m) dp[i][0] = i        // 全刪
    for (j in 0..n) dp[0][j] = j        // 全插
    for (i in 1..m) {
        for (j in 1..n) {
            dp[i][j] = if (word1[i - 1] == word2[j - 1]) {
                dp[i - 1][j - 1]        // 字元相同，不花操作
            } else {
                1 + minOf(
                    dp[i - 1][j],        // 刪
                    dp[i][j - 1],        // 插
                    dp[i - 1][j - 1]     // 改
                )
            }
        }
    }
    return dp[m][n]
}

NOTE

換個視角，編輯距離其實是網格圖上的最短路徑：把 (i, j) 當節點，「刪/插/改」是權重 1 的邊、「字元相同」是權重 0 的邊，求左上到右下的最短路。許多 2D DP 都能這樣翻譯成圖問題——這也是 DP 與最短路演算法的共通血緣。

空間優化

網格與雙序列型若 dp[i][*] 只依賴 dp[i-1][*]，可把二維壓成一維滾動陣列，空間從 O(mn) 降到 O(n)。

跨倉庫導讀

#10Regular Expression MatchingHard★★★★★⏱ O(m * n)#44Wildcard MatchingHard★★★★★⏱ O(m·n)#62Unique PathsMedium★★★★★⏱ O(m * n)#63Unique Paths IIMedium★★★★★⏱ O(m * n)#64Minimum Path SumMedium★★★★★⏱ O(m * n)#72Edit DistanceMedium★★★★★⏱ O(m * n)#97Interleaving StringMedium★★★★★⏱ O(m * n)#115Distinct SubsequencesHard★★★★★⏱ O(m * n)#123Best Time to Buy and Sell Stock IIIHard★★★★★⏱ O(n)#174Dungeon GameHard★★★★★⏱ O(m·n)#188Best Time to Buy and Sell Stock IVHard★★★★★⏱ O(n·k)#221Maximal SquareMedium★★★★★⏱ O(m * n)#309Best Time to Buy and Sell Stock with CooldownMedium★★★★★⏱ O(n)#312Burst BalloonsHard★★★★★⏱ O(n^3)#329Longest Increasing Path in a MatrixHard★★★★★⏱ O(m * n)#474Ones and ZeroesMedium★★★★★⏱ O(k * m * n)#494Target SumMedium★★★★★⏱ O(n * target)#516Longest Palindromic SubsequenceMedium★★★★★⏱ O(n^2)#518Coin Change IIMedium★★★★★⏱ O(n * amount)#877Stone GameMedium★★★★★⏱ O(1)#879Profitable SchemesHard★★★★★⏱ O(plans * n * minProfit)#920Number of Music PlaylistsHard★★★★★⏱ O(goal * n)#926Flip String to Monotone IncreasingMedium★★★★★⏱ O(n)#1049Last Stone Weight IIMedium★★★★★⏱ O(n * sum)#1140Stone Game IIMedium★★★★★⏱ O(n^3)#1143Longest Common SubsequenceMedium★★★★★⏱ O(m * n)#1220Count Vowels PermutationHard★★★★★⏱ O(n)#1547Minimum Cost to Cut a StickHard★★★★★⏱ O(c^3)#1639Number of Ways to Form a Target String Given a DictionaryHard★★★★★⏱ O(m * n)#1866Number of Ways to Rearrange Sticks With K Sticks VisibleHard★★★★★⏱ O(n * k)#1911Maximum Alternating Subsequence SumMedium★★★★★⏱ O(n)#2218Maximum Value of K Coins from PilesHard★★★★★⏱ O(n * k * max_pile_size)