# **程式筆記(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]
```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]
```
```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)
```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
```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]
```
---
**: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
```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術語即是
```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`
Sign in with Wallet
Connect another wallet