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

Notes:

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

跨倉庫導讀#

#10 Regular Expression Matching #62 Unique Paths #63 Unique Paths II #64 Minimum Path Sum #72 Edit Distance #97 Interleaving String #115 Distinct Subsequences #221 Maximal Square #309 Best Time to Buy and Sell Stock with Cooldown #312 Burst Balloons #329 Longest Increasing Path in a Matrix #474 Ones and Zeroes #494 Target Sum #516 Longest Palindromic Subsequence #518 Coin Change II #877 Stone Game #879 Profitable Schemes #920 Number of Music Playlists #926 Flip String to Monotone Increasing #1049 Last Stone Weight II #1140 Stone Game II #1143 Longest Common Subsequence #1220 Count Vowels Permutation #1547 Minimum Cost to Cut a Stick #1639 Number of Ways to Form a Target String Given a Dictionary #1866 Number of Ways to Rearrange Sticks With K Sticks Visible #2218 Maximum Value of K Coins from Piles #5782 Maximum Alternating Subsequence Sum