---
# System prepended metadata

title: '**程式筆記(dynamic programming 2)**'
tags: [code, note, dynamic programming]

---

# **程式筆記(dynamic programming 2)**


:::info
:information_source: 日期 : 2023/07/20
:::



---

**:thumbsup:DP(bottom-up + 二維陣列)**

**Number**

* 走格子
用數學原理去想，先把出發點周圍兩面都換成1，後來再累加的方式往上加
```python
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
```

* Minimum Path Sum
從左上走到右下，到終點時，回傳路徑最小的和
邊界條件直接窮舉
dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + dp[i][j]
![image](https://hackmd.io/_uploads/Byr8KFKlJe.png =30%x)

```python
class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        dp = [[0] * (n) for _ in range(m)]

        for i in range(m):
            for j in range(n):
                if i == 0 and j == 0:
                    dp[i][j] = grid[i][j]
                elif i == 0:
                    dp[i][j] = grid[i][j] + dp[i][j - 1]
                elif j == 0:
                    dp[i][j] = grid[i][j] + dp[i - 1][j]
                else: 
                    dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]
        
        return dp[m - 1][n - 1]
```


* Partition Equal Subset Sum (subset內部相加)
```
dp[i][a] = i為數字index a為amount(待組成數量)
dp = (nums + 1) * (amount + 1)

選擇該數字和不選擇該數字
如果數字值比a小 
1. 選擇數字 = dp[i - 1][a - n] (前 i - 1 個元素可以達成總和 a - nums[i - 1])
2. 不選擇數字 = dp[i - 1][a] (前 i - 1 個元素已經可以形成總和 a)
如果數字比a大
1. 不選擇數字 =  dp[i - 1][a]
```
![](https://hackmd.io/_uploads/ryN8aUrw2.png)
```python
class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        if sum(nums) % 2 != 0:
            return False
        
        amount = sum(nums) // 2
        dp = [[False] * (amount + 1) for _ in range(len(nums) + 1)] # (nums + 1) * (amount + 1)
        for i in range(len(nums) + 1):
            dp[i][0] = True

        for i in range(1, len(nums) + 1):
            for a in range(1, amount + 1):
                n = nums[i - 1]
                if a >= n:
                    dp[i][a] = dp[i - 1][a] or dp[i - 1][a - n]
                else:
                    dp[i][a] = dp[i - 1][a]
        
        return dp[len(nums)][amount]

```
也可以用一維解
```python
class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        total = sum(nums)
        if total % 2:
            return False

        half = total // 2
        dp = [False] * (half + 1)
        dp[0] = True

        for n in nums:
            dp_new = dp[:] # 確保當前的dp 不受當前n影響
            for j in range(1, half + 1):
                if n <= j:
                    dp_new[j] = dp_new[j] or dp[j - n]
            dp = dp_new
        
        return dp[half]
```


**String**

```
如果當看到兩個string需要交叉比對或互相對應時，
就可以用二維的陣列去保存
```

* Longest Common Subsequence
dp[i]意義到i這個字母為止的"最佳 最長"subsequence
斜對角方向移動 -> 陣列斜對角，才是兩string每個字母一一對應(到目前為止，對應到的字母的次數)
橫向或直向移動 -> 那就只是某一個string的"同一個字母"對應(繼承別人的最佳解)
(橫向: 移除上面string的c / 縱向: 移除左邊string的c)

![](https://hackmd.io/_uploads/BJbjndUq2.png =75%x)

```python
class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        n, m = len(text1), len(text2)
        dp = [[0] * (m + 1) for _ in range(n + 1)] # (n + 1) * (m + 1)

        for i in range(1, n + 1):
            for j in range(1, m + 1):
                if text1[i - 1] == text2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1] + 1
                else:
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
        
        return dp[n][m]
```


* Interleaving String (交叉組成string)
判斷字串 s1、s2是否能夠交錯形成 s3
```python
左邊是s1，是i
右邊是s2，是j
     0  1  2  3  4  5
     d  b  b  c  a
0 a  T  F  F  F  F  F
1 a  T  F  F  F  F  F 
2 b  T  T  T  T  T  F
3 c  F  T  T  F  T  F 
4 c  F  F  T  T  T  T
5    F  F  F  F  F  T

這是s3
0123456789
aadbbcbcac
```
```python
if i < len(s1) and s1[i] == s3[i + j] and dp[i + 1][j]:
    dp[i][j] = True
if j < len(s2) and s2[j] == s3[i + j] and dp[i][j + 1]:
    dp[i][j] = True
```
```python
s1[i] == s3[i + j] 意思是如果s[i]和s3的某個字有對到，
而且剛好接在當前j的後面(所以會是i + j)
-> 會有j的原因是因為要接續j繼續排，所以j數值是固定的

dp[i + 1][j] = True 意思是如果上一個(i + 1) s1的字，
已經被走用了(從背後開始走)，且為 True，必須要被用過了，不然不算(因為要按照順序用)
-> 規定要按造順序走，s1和s2都不能跳
-> 所以上一格為true才可走
```

```python
# Top-Down

class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        n, m = len(s1), len(s2)
        if n + m != len(s3):
            return False
            
        dp = [[False] * (m + 1) for _ in range(n + 1)]
        dp[n][m] = True

        for i in range(n, -1, -1):
            for j in range(m, -1, -1):
                # 兩種情況
                if i + 1 <= n and s3[i + j] == s1[i] and dp[i + 1][j]:
                    dp[i][j] = True
                if j + 1 <= m and s3[i + j] == s2[j] and dp[i][j + 1]:
                    dp[i][j] = True
        
        return dp[0][0]
```

```python
# Bottom-Up

class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        n, m = len(s1), len(s2)
        if n + m != len(s3):
            return False
            
        dp = [[False] * (m + 1) for _ in range(n + 1)] # (n + 1) * (m + 1)
        dp[0][0] = True

        for i in range(0, n + 1):
            for j in range(0, m + 1):
                # 兩種情況
                if i > 0 and s1[i - 1] == s3[i + j - 1] and dp[i - 1][j]:
                    dp[i][j] = True
                if j > 0 and s2[j - 1] == s3[i + j - 1] and dp[i][j - 1]:
                    dp[i][j] = True
        
        return dp[n][m]
```





* Longest Arithmetic Subsequence
找到longest arithmetic subsequence，A sequence seq is arithmetic if seq[i + 1] - seq[i] are all the same value
![image](https://hackmd.io/_uploads/BJRrTocekg.png =50%x)

```python
class Solution:
    def longestArithSeqLength(self, nums: List[int]) -> int:
        # (starting num, diff) : accumu length
        hashmap = collections.defaultdict(int)

        for i in range(len(nums)):
            for j in range(0, i):
                diff = nums[i] - nums[j]
                # 兩個number組成的diff 初始長度會是1
                if (j, diff) not in hashmap:
                    hashmap[(j, diff)] = 1
                hashmap[(i, diff)] = hashmap[(j, diff)] + 1
        
        return max(hashmap.values())
```

---

**:thumbsup:coin change** 

```
dp[ci][a] = ci為硬幣index a為amount(待組成數量)
dp = (coins + 1) * (amount + 1)

選擇該硬幣和不選擇該硬幣
如果coin幣值比a小
1. 選擇coin = dp[ci][a - c] (加入前面序列的組合)
2. 不選擇coin = dp[ci - 1][a] (繼承上面coin的amount 這個amount的最佳解)  
如果coin幣值比a大
1. 不選擇coin  =  dp[ci - 1][a]
```

* coin change
希望找到最小組成數量
```
coin change
0 amount 有 0 總組合方法
dp[c][a] = min(dp[c - 1][a] (不選c), dp[c][a - coin] + 1 (選c))
```
```python
class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [[float("inf")] * (amount + 1) for _ in range(len(coins) + 1)] # (coins + 1) * (amount + 1)
        # initial for 0 amount
        for c in range(len(coins) + 1):
            dp[c][0] = 0

        for c in range(1, len(coins) + 1):
            for a in range(amount + 1):
                coin = coins[c - 1]
                if coin <= a:
                    dp[c][a] = min(dp[c - 1][a], dp[c][a - coin] + 1)
                else:
                    dp[c][a] = dp[c - 1][a]
        
        return dp[len(coins)][amount] if dp[len(coins)][amount] != float("inf") else -1
```



* coin change II
希望找到有幾總組成方法
```
Input: amount = 5, coins = [1,2,5]
Output: 4
Explanation: there are four ways to make up the amount:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
```

```
coin change II
0 amount 有 1 總組合方法 (都不選)
dp[c][a] = dp[c][a - coin] + dp[c - 1][a]
```

```python
class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        n = len(coins)
        dp = [[0] * (amount + 1) for _ in range(n + 1)]
        # 初始化amount = 0
        for i in range(n + 1):
            dp[i][0] = 1
        
        for c in range(1, n + 1):
            for a in range(1, amount + 1):
                coin = coins[c - 1]
                if a >= coin:
                    dp[c][a] = dp[c][a - coin] + dp[c - 1][a]
                else:
                    dp[c][a] = dp[c - 1][a]
        
        return dp[n][amount]
```
![](https://hackmd.io/_uploads/S1m04085h.png =80%x)


---


**:thumbsup:DP (dfs優化)** 
```python
這類dfs要優化，就是要用動態規劃的memoization
```

* Target Sum
給定一串nums，可加正負號到num上，問有幾種方法可以排列成target
用掉某一個數字(n)時，有兩個選擇，
```python
1. 把數字加上負號，代表減去
dfs(index + 1, total - n)
2. 把數字加上正號，代表加上
dfs(index + 1, total + n)

index + 1，代表要往下一個index前進
```
**這類dfs要優化，就是要用動態規劃的caching，caching中會儲存(index, total)**，如果某一條路剩下的index和total相同，那它接下來的路徑與路徑數必定會像其他相同index和total的人，故可以直接承接它的total

* Edit Distance
用memoization去優化，因為我們會走到重複的步驟


```python
class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        n, m = len(word1), len(word2)
        memo = [[-1] * m for _ in range(n)]
        return self.traverse(word1, word2, 0, 0, memo)

    def traverse(self, word1, word2, i, j, memo):
        if i == len(word1) and j == len(word2):
            return 0
        if i == len(word1):
            return len(word2) - j
        if j == len(word2):
            return len(word1) - i
        if memo[i][j] != -1:
            return memo[i][j]
        
        if word1[i] != word2[j]:
            replace = self.traverse(word1, word2, i + 1, j + 1, memo) + 1
            delete = self.traverse(word1, word2, i + 1, j, memo) + 1
            insert = self.traverse(word1, word2, i, j + 1, memo) + 1
            memo[i][j] = min(replace, delete, insert)
        else:
            no_change = self.traverse(word1, word2, i + 1, j + 1, memo)
            memo[i][j] = no_change
        
        return memo[i][j]
```

一般dfs (優化前)
```python
class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        self.min_cost = float("inf")
        self.traverse(word1, word2, 0, 0, 0)
        return self.min_cost

    def traverse(self, word1, word2, i, j, cost):
        if i == len(word1) and j == len(word2):
            self.min_cost = min(self.min_cost, cost)
            return
        if i == len(word1):
            self.min_cost = min(self.min_cost, cost + len(word2) - j)
            return 
        if j == len(word2):
            self.min_cost = min(self.min_cost, cost + len(word1) - i)
            return
        
        if word1[i] != word2[j]:
            self.traverse(word1, word2, i + 1, j + 1, cost + 1) # replace
            self.traverse(word1, word2, i + 1, j, cost + 1) # delete
            self.traverse(word1, word2, i, j + 1, cost + 1) # insert
        else:
            self.traverse(word1, word2, i + 1, j + 1, cost)
```

---



**:thumbsup:其他dp** 

* 最大正方形
dp[i][j]的意義為 以i, j位置為右下角頂點的其他三點 可以組成的正方形邊長
最左和最上面初始化dp = matrix
![](https://hackmd.io/_uploads/S1Gd0oHv2.png)
```python
if matrix[i][j] = 1,
dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1


class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        m, n = len(matrix), len(matrix[0])
        record = [[0] * (n) for _ in range(m)] # 儲存新數字用 m * n
        res = 0 # 最大數字

        # 左
        for i in range(m):
            record[i][0] = int(matrix[i][0])
            res = max(res, record[i][0])
        # 右
        for j in range(n):
            record[0][j] = int(matrix[0][j])
            res = max(res, record[0][j])

        for i in range(1, m):
            for j in range(1, n):
                if int(matrix[i][j]) > 0:
                    record[i][j] = min(record[i - 1][j - 1], record[i - 1][j], record[i][j - 1]) + 1
                res = max(res, record[i][j])
        
        return res * res
```

* Target Sum
dp[i][j] 表示使用nums[1 ~ i]的數字，能夠組成加總為j的數量
舉例下圖第三列(index 2)，如果再多加一個1進來(變(1, 1))，可以組成0的情況，為原本(1)擁有的total，再加1或減1，換成dp術語即是
![](https://hackmd.io/_uploads/rkv7b3Dqh.png =80%x)
```python
dp[2][total - 1] += dp[1][total]
dp[2][total + 1] += dp[1][total]

dp[現在的index][total - 現在數值] += dp[上一個index][total]
cnt = dp[i][total]
```
時間複雜度為O(N * total_sum)，其中N是nums列表中的元素數量，total_sum是nums列表的總和。會比dfs + caching優化很多








**講解連結**

Provided by. 

###### tags: `dynamic programming` `note` `code`