2D Dynamic Programming

二維動態規劃用轉移矩陣分析。

• 62. Unique Paths

Bottom-Up每隔是右與下加總取第一格，採用Top-Down寫法就是左與上的轉移方程式，取最後一格，因為要加總，起始為0。

• 1143. Longest Common Subsequence

i, j符合可以向右下走，不合看右或下

C跟B不合看右或下
右： e 跟bcde比
下： c 跟cde比
3表示有3個符合

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        n, m = len(text1), len(text2)
        
        M = [[0 for j in range(m+1)] for i in range(n+1)]
        for i in range(n-1, -1, -1):
            for j in range(m-1, -1, -1):
                if text1[i] == text2[j]:
                    M[i][j] = M[i+1][j+1] + 1
                else:
                    M[i][j] = max(M[i][j+1], M[i+1][j])
        return M[0][0]

• 518. Coin Change II

多重選取幣值，要到目標價格。
最右 1, 1, 1，從右下角填表至左上角，每點看右與下加總，左上角是結果，用採用Top-Down寫法

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        dp = [0] * (amount + 1)
        dp[0] = 1
        for coin in coins:
            for i in range(coin, amount + 1):
                dp[i] += dp[i - coin]

        return dp[-1]

Image Credits: Neetcode

---

如果你覺得這篇文章很棒，請你不吝點讚 (ﾟ∀ﾟ)