# 2-D Dynamic Programming (11)
> 紀錄 NeetCode-150 與 LeetCode 的解題想法、刷題過程與錯誤，以 Python 或 C++ 兩種語言為主
>
> 其他 NeetCode-150 或 LeetCode 的主題請見 [Here](https://hackmd.io/-ovTFlzLRWaSgzDGhbSwsA)
<!-- 常用色碼紀錄
Easy: <font color="#00ad5f">**Easy**</font>
Medium: <font color="#ffbb00">**Medium**</font>
Hard: <font color="#ee2f56">**Hard**</font>
-->
所謂的 2-D dynamic programming 看起來不只是 2-D 的 memorization array，而是在 DP 的遞迴中有兩個控制參數。
## 1. Unique Paths
<font color="#ffbb00">**Medium**</font>
> There is an `m x n` grid where you are allowed to move either down or to the right at any point in time.
>
> Given the two integers `m` and `n`, return the number of possible unique paths that can be taken from the top-left corner of the grid (`grid[0][0]`) to the bottom-right corner (`grid[m - 1][n - 1]`).
>
> You may assume the output will fit in a 32-bit integer.
### Example 1:
```java
Input: m = 3, n = 6
Output: 21
```
### Example 2:
```java
Input: m = 3, n = 3
Output: 6
```
### Constraints
* `1 <= m, n <= 100`
### Solution
排列組合的加法原理
```pthon=
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
if m == 1 and n == 1:
return 1
M = [[0 for _ in range(n)] for _ in range(m)]
# bounary
for r in range(m):
if r == 0:
for c in range(1, n):
M[r][c] = 1
else:
M[r][0] = 1
for r in range(1, m):
for c in range(1, n):
M[r][c] = M[r][c-1] + M[r-1][c]
return M[m-1][n-1]
```
### Complexity
* Time complexity: $O(m \cdot n)$
* Space complexity: $O(m \cdot n)$
## 2. Longest Common Subsequence
<font color="#ffbb00">**Medium**</font>
> Given two strings `text1` and `text2`, return the length of the longest common subsequence between the two strings if one exists, otherwise return `0`.
>
> A subsequence is a sequence that can be derived from the given sequence by deleting some or no elements without changing the relative order of the remaining characters.
>
> * For example, `"cat"` is a subsequence of `"crabt"`.
>
> A **common subsequence** of two strings is a subsequence that exists in both strings.
### Example 1:
```java
Input: text1 = "cat", text2 = "crabt"
Output: 3
```
Explanation: The longest common subsequence is "cat" which has a length of 3.
### Example 2:
```java
Input: text1 = "abcd", text2 = "abcd"
Output: 4
```
### Example 3:
```java
Input: text1 = "abcd", text2 = "efgh"
Output: 0
```
### Constraints
* `1 <= text1.length, text2.length <= 1000`
* `text1` and `text2` consist of only lowercase English characters.
### Solution
將兩字串中的字元依序比對，依序對應字元是否相同可拆解成兩種不同的子問題
* 若某字元相同，則同時往後一個繼續比較 substring/subproblem
* 若某字元不同，則彼此往後一個交叉比較 substring/subproblem
以 Example 1 為例，比較 `"s1 = cat"` 與 `"s2 = crabt"` 兩字串
* `s1[0] = 'c' == 'c' = s2[0]`
* index = 0 時對應字元相同，繼續比較 index 1 至結束
* 比較子問題 `s1[1:]` 與 `s2[1:]`
* `s1[1] = 'a' != 'r' = s2[1]`
* index = 1 時對應字元不同，交叉比較 substring/subproblem
* 比較子問題 `s1[1:]` 與 `s2[2:]`
* 比較子問題 `s1[2:]` 與 `s1[1:]`
為了實現子問題的，可將上述子問題的拆解以二維矩陣視覺化
* 當對應字元相同，兩者同時退一位，所以會往右下的對角線(綠箭頭)繼續找 subproblem
* 當對應字元不同，兩者彼此退一位交叉比較，所以會往右或下(藍箭頭)繼續找 subproblem
* 以棕色方框的 No 為例，就是比較 `"bat"` 與 `"t"` 兩個 subproblem，且因為 `'b' != 't'`，所以往右或下繼續比較
因為 DP 就是找數學歸納法的步驟，以此題為例，當字元相同時代表該位置有貢獻，需查看他的前一步貢獻(最長子序列)是多少，因此必須從末端往回推(紅色箭頭)
* 該位置有貢獻(1)，找前一個對角線位置的值 + 1
* 該位置沒貢獻(No)，找右或下的表格取最大值
```python=
class Solution:
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
ROWS = len(text1)
COLS = len(text2)
M = [[0 for _ in range(COLS + 1)] for _ in range(ROWS + 1)]
for r in range(ROWS - 1, -1, -1):
for c in range(COLS - 1, -1, -1):
if text1[r] == text2[c]:
M[r][c] = 1 + M[r+1][c+1]
else:
M[r][c] = max(M[r+1][c], M[r][c+1])
return M[0][0]
```
### Complexity
* Time complexity: $O(m \cdot n)$
* Space complexity: $O(m \cdot n)$
## 3. Best Time to Buy and Sell Stock with Cooldown
<font color="#ffbb00">**Medium**</font>
> You are given an integer array `prices` where `prices[i]` is the price of NeetCoin on the `ith` day.
>
> You may buy and sell one NeetCoin multiple times with the following restrictions:
>
> * After you sell your NeetCoin, you cannot buy another one on the next day (i.e., there is a cooldown period of one day).
> * You may only own at most one NeetCoin at a time.
>
> You may complete as many transactions as you like.
>
> Return the **maximum profit** you can achieve.
### Example 1:
```java
Input: prices = [1,3,4,0,4]
Output: 6
```
Explanation: Buy on day 0 (price = 1) and sell on day 1 (price = 3), profit = 3-1 = 2. Then buy on day 3 (price = 0) and sell on day 4 (price = 4), profit = 4-0 = 4. Total profit is 2 + 4 = 6.
### Example 2:
```java
Input: prices = [1]
Output: 0
```
### Constraints
* `1 <= prices.length <= 5000`
* `0 <= prices[i] <= 1000`
### Solution
* 每個時間點(index = i)都會有一種狀態 buy 或 sell
* 每個時間點(index = i)可以選擇下一刻的狀態，但須滿足下列限制
* 若 `(i, buy)`，則下一刻可以是 `(i + 1, sell)` 或 `(i + 1, cooldown)`
* 若 `(i, sell)`，則下一刻只能是 `(i + 2, buy)`(因為賣出隔天不能買)或 `(i + 1, cooldown)`
* cooldown 等同於狀態不變，持續前一刻的狀態
* 每個時間點有兩種選擇，選擇可產生最大利潤(prifit)的狀態
* 當選擇 index = i 的時間選擇 sell 表示賣出股票，收入 `+ prices[i]`
* 當選擇 index = i 的時間選擇 buy 表示買入股票，收入 `- prices[i]`
根據上述規則可以視覺化樹狀圖如下
```python=
class Solution:
def maxProfit(self, prices: List[int]) -> int:
# True/False for buy/sell
M = {} # (i-th day, buy/sell): profit
def dp(i, buying):
if i >= len(prices):
return 0
if (i, buying) in M:
return M[(i, buying)]
if buying: # buy on i-th day
profit = dp(i + 1, not buying) - prices[i] # sell on next day
cooldown = dp(i + 1, buying) # cooldown on next day
profit = max(profit, cooldown)
else: # sell on i-th day
profit = dp(i + 2, not buying) + prices[i] # buy on the day after tomorrow
cooldown = dp(i + 1, buying) # cooldown on next day
profit = max(profit, cooldown)
M[(i, buying)] = profit
return M[(i, buying)]
return dp(0, True)
```
### Complexity
* Time complexity: $O(n)$
* Space complexity: $O(n)$
## 4. Coin Change ll
<font color="#ffbb00">**Medium**</font>
> You are given an integer array `coins` representing coins of different denominations (e.g. 1 dollar, 5 dollars, etc) and an integer `amount` representing a target amount of money.
>
> Return the number of distinct combinations that total up to `amount`. If it's impossible to make up the amount, return `0`.
>
> You may assume that you have an unlimited number of each coin and that each value in `coins` is unique.
### Example 1:
```java
Input: amount = 4, coins = [1,2,3]
Output: 4
```
Explanation:
* 1+1+1+1 = 4
* 1+1+2 = 4
* 2+2 = 4
* 1+3 = 4
### Example 2:
```java
Input: amount = 7, coins = [2,4]
Output: 0
```
### Constraints
* `1 <= coins.length <= 100`
* `1 <= coins[i] <= 1000`
* `0 <= amount <= 1000`
### Solution
#### 1. Basic
* 避免重複選取，可以先對 coins 做排序，使得可行解以遞增的方排排序
* 為了避免重複選取，硬幣也是以遞增的方式選取
* Ex. 某個時間點選 coins[i] 硬幣，則下一輪選取的時候也只能從 coins[i] 開始選擇，不能再拿 coins[i-1]
以上述規則畫出的樹狀圖如下
這種方式的 DP 遞迴會有兩個參數，記憶矩陣也會是二維矩陣，因為要同時紀錄當下的剩餘金額以及從第 i 個硬幣開始選取。
```python=
class Solution:
def change(self, amount: int, coins: List[int]) -> int:
coins.sort()
M = [[-1 for _ in range(len(coins))] for _ in range(amount + 1)]
def dp(amt, startIdx):
if amt == 0:
M[amt][startIdx] = 1
return M[amt][startIdx]
if M[amt][startIdx] == -1:
res = 0
for i in range(startIdx, len(coins)):
if amt - coins[i] >= 0:
res += dp(amt - coins[i], i)
M[amt][startIdx] = res
return M[amt][startIdx]
return dp(amount, 0)
```
針對每一個剩餘金額，選取硬幣時都要迭代整個 coins，所以時間複雜度為 $O(m \cdot n^2)$，其中 m = amount，n = len(coins)
#### 2. Improvement
改善方式可以將硬幣選擇的迭代改為二選一。每個時間點將硬幣的選擇分為兩種狀況
* 選擇 coins[i] 硬幣
* 不選擇 coins[i] 硬幣，改為 coins[i+1] 硬幣
```python=
class Solution:
def change(self, amount: int, coins: List[int]) -> int:
coins.sort()
M = [[-1 for _ in range(len(coins))] for _ in range(amount + 1)]
def dp(amt, startIdx):
if amt == 0:
return 1
if startIdx >= len(coins):
return 0
if M[amt][startIdx] != -1:
return M[amt][startIdx]
res = 0
if amt >= coins[startIdx]:
res = dp(amt - coins[startIdx], startIdx) # use this coin
res += dp(amt, startIdx + 1) # use next coin
M[amt][startIdx] = res
return M[amt][startIdx]
return dp(amount, 0)
```
### Complexity
* Time complexity: $O(m \cdot n)$
* m is amount
* n is length of coins
* Space complexity: $O(m \cdot n)$
## 5. Target Sum
<font color="#ffbb00">**Medium**</font>
> You are given an array of integers `nums` and an integer `target`.
>
> For each number in the array, you can choose to either add or subtract it to a total sum.
> * For example, if `nums = [1, 2]`, one possible sum would be `"+1-2=-1"`.
>
> If `nums=[1,1]`, there are **two different ways** to sum the input numbers to get a sum of `0`: `"+1-1"` and `"-1+1"`.
>
> Return the number of different ways that you can build the expression such that the total sum equals `target`.
### Example 1:
```java
Input: nums = [2,2,2], target = 2
Output: 3
```
Explanation: There are 3 different ways to sum the input numbers to get a sum of 2.
`+2 +2 -2 = 2`
`+2 -2 +2 = 2`
`-2 +2 +2 = 2`
### Constraints
* `1 <= nums.length <= 20`
* `0 <= nums[i] <= 1000`
* `-1000 <= target <= 1000`
### Solution
nums 中的每個元素都有兩種可能，把所有可能解列出如下，當有相同和與相同選擇時再輔以 DP 解。要同時紀錄當下的總和以及目前輪到哪個 nums 中的哪個元素做選擇，所以 DP 的遞迴函式會有兩個參數，同樣的記憶矩陣也是二維矩陣 len(nums) * (a * target + 1)。
但如果以矩陣的方式儲存已經出現過的值，可能會超出矩陣的 index，因為當前總和可能 < 0，但矩陣的 index 不會 < 0。若是用矩陣儲存出現過的值，當 index < 0 時需要使用偏移(offset)做修正，但會比較麻煩。
可以改以 hash map 的方式將對應的 (i, currentSum):count 儲存。
```python=
class Solution:
def findTargetSumWays(self, nums: List[int], target: int) -> int:
M = {} # (index, currentSum)
def dp(i, currentSum):
if i == len(nums):
return 1 if currentSum == target else 0
if (i, currentSum) in M:
return M[(i, currentSum)]
M[(i, currentSum)] = dp(i + 1, currentSum + nums[i]) + dp(i + 1, currentSum - nums[i])
return M[(i, currentSum)]
return dp(0, 0)
```
### Complexity
* Time complexity: $O(m \cdot n)$
* m is sum og nums
* n is length of nums
* Space complexity: $O(m \cdot n)$
## 6. Interleaving String
<font color="#ffbb00">**Medium**</font>
> You are given three strings `s1`, `s2`, and `s3`. Return `true` if `s3` is formed by interleaving `s1` and `s2` together or false otherwise.
>
> **Interleaving** two strings `s` and `t` is done by dividing `s` and `t` into `n` and `m` substrings respectively, where the following conditions are met
>
> * `|n - m| <= 1`, i.e. the difference between the number of substrings of `s` and `t` is at most `1`.
> * `s = s1 + s2 + ... + sn`
> * `t = t1 + t2 + ... + tm`
> * **Interleaving** `s` and `t` is `s1 + t1 + s2 + t2 + ...` or `t1 + s1 + t2 + s2 + ...`
>
> You may assume that `s1`, `s2` and `s3` consist of lowercase English letters.
### Example 1:
```java
Input: s1 = "aaaa", s2 = "bbbb", s3 = "aabbbbaa"
Output: true
```
Explanation: We can split `s1` into `["aa", "aa"]`, `s2` can remain as `"bbbb"` and `s3` is formed by interleaving `["aa", "aa"]` and `"bbbb"`.
### Example 2:
```java
Input: s1 = "", s2 = "", s3 = ""
Output: true
```
### Example 3:
```java
Input: s1 = "abc", s2 = "xyz", s3 = "abxzcy"
Output: false
```
Explanation: We can't split `s3` into `["ab", "xz", "cy"]` as the order of characters is not maintained.
### Constraints
* `0 <= s1.length, s2.length <= 50`
* `0 <= s3.length <= 100`
### Solution
以變數 `i` 控制字串 `s1`，變數 `j` 控制字串 `s2`，變數 `k` 控制字串 `s3`。理論上要三個變數來控制三個字串中目前各自正在處理的字元，但因為 `s3` 是由 `s1` 與 `s2 `交錯組合形成，所以 `s3` 的控制變數 `k` 可以由 `s1` 的 `i` 與 `s2` 的 `j` 相加得到。
以 Example 1 為例:
* 當 `i = 2` 時表示正在處理 `s1[3] = 2`
* 當 `j = 1` 時表示正在處理 `s2[1] = b`
* 此時正在處理目標字串 `s3` 的 `s3[4] = b`，因此 `k = i + j`
#### 1. Recursion ver.
每次移動指標 `i` 或 `j` 讓字串 `s1` 或 `s2` 跟 `s3` 配對，如果可以配對成功表示這個字元可以匹配，不行表示需要換另一個字串，可列樹狀圖如下:
每次可選擇往 `i` 或 `j` 前進，如果可以繼續往下走，則該點回傳 `True`，反之回傳 `False`。
```python=
# Recursion ver.
class Solution:
def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
if len(s1) + len(s2) != len(s3):
return False
M = {} # (i, j):True/False where i for s1 and j for s2
def dp(i, j):
# base condition
if i == len(s1) and j == len(s2):
return True
# memorization
if (i, j) in M:
return M[(i, j)]
if i < len(s1) and s1[i] == s3[i+j] and dp(i + 1, j):
M[(i, j)] = True
return M[(i, j)]
if j < len(s2) and s2[j] == s3[i+j] and dp(i, j + 1):
M[(i, j)] = True
return M[(i, j)]
M[(i, j)] = False
return M[(i, j)]
return dp(0, 0)
```
#### 2. Ieration ver.
(1) 迭代版本表格如下。基礎條件是當兩個字串當處理完成(右下角)時回傳 `True`。
(2) 每一個 cell 去分別對應目前剩餘的 `s1` 字串與 `s2` 字串。
如果 `s1` 配對成功(True)，往下走繼續配對；如果 `s2` 配對成功，往右走繼續配對。
(3) 某一個 cell 能否配對成功應該要看他的下一個位置(右/下)，如果右或下有其中一個為 True，表示該條路徑可行(True)，如果右/下都為 True，表示該條路徑不可行(True)。因此需要從字串尾端逆推回來。
```python=
# Iteration ver.
class Solution:
def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
if len(s1) + len(s2) != len(s3):
return False
M = [[False for _ in range(len(s2) + 1)] for _ in range(len(s1) + 1)]
M[len(s1)][len(s2)] = True
for i in range(len(s1), -1, -1):
for j in range(len(s2), -1, -1):
# check bottom
if i < len(s1) and s1[i] == s3[i+j] and M[i+1][j]:
M[i][j] = True
# check right
if j < len(s2) and s2[j] == s3[i+j] and M[i][j+1]:
M[i][j] = True
return M[0][0]
```
### Complexity
* Time complexity: $O(m \times n)$
* m is the length of s1
* n is the length of s2
* Space complexity: $O(m \times n)$
## 7. Longest Increasing Path in Matrix
<font color="#ee2f56">**Hard**</font>
> You are given a 2-D grid of integers `matrix`, where each integer is greater than or equal to `0`.
>
> Return the length of the longest strictly increasing path within `matrix`.
>
> From each cell within the path, you can move either horizontally or vertically. You **may not** move **diagonally**.
### Example 1:
```java
Input: matrix = [[5,5,3],[2,3,6],[1,1,1]]
Output: 4
```
Explanation: The longest increasing path is `[1, 2, 3, 6]` or `[1, 2, 3, 5]`.
### Example 2:
```java
Input: matrix = [[1,2,3],[2,1,4],[7,6,5]]
Output: 7
```
Explanation: The longest increasing path is `[1, 2, 3, 4, 5, 6, 7]`.
### Constraints
* `1 <= matrix.length, matrix[i].length <= 100`
### Solution
以暴力解來看，每個 cell 都有 4 個方向可走，整個矩陣會有 $m \times n$ 個 cells，因此複雜度為 $4^{m \times n}$。又因為每個 cell 都可能當作起點出發找最長路徑，因此總時間複雜度為 $m \times n \times 4^{m \times n}$。
但實際上，如果使用 DP 後加入 memorization 表格，因為每個從每個點出發的最長路徑都會被紀錄(有計算過的話)，所以暴力解的複雜度可以降至 $O(m \times n)$。
遞迴循環中，符合條件的情況(以下)
* 不超過 memorization table 的 index 大小
* 下一個 cell 的值 > 目前 cell 的值
才能往前，否則該點不能行走，回傳路徑長為 `0`。每個點的四個方向都要迭代一次。因為要紀錄目前 cell 的值，所以遞迴函式需要多一個參數傳遞。
```python=
class Solution:
def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
ROWS = len(matrix)
COLS = len(matrix[0])
M = [[-1 for _ in range(COLS)] for _ in range(ROWS)]
def dp(r, c, currentValue):
if (r < 0 or r >= ROWS or
c < 0 or c >= COLS or
matrix[r][c] <= currentValue):
return 0
if M[r][c] != -1:
return M[r][c]
res = 1
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
for dr, dc in directions:
newR, newC = r + dr, c + dc
res = max(res, 1 + dp(newR, newC, matrix[r][c]))
M[r][c] = res
return M[r][c]
res = 0
for r in range(ROWS):
for c in range(COLS):
dp(r, c, -1)
res = max(res, M[r][c])
return res
```
### Complexity
* Time complexity: $O(m \times n)$
* m is the row of matrix
* n is the column of matrix
* Space complexity: $O(m \times n)$
## 8. Distinct Subsequence
<font color="#ee2f56">**Hard**</font>
> You are given two strings `s` and `t`, both consisting of english letters.
>
> Return the number of distinct **subsequences** of `s` which are equal to `t`.
### Example 1:
```java
Input: s = "caaat", t = "cat"
Output: 3
```
Explanation: Rhere are 3 ways you can generate `"cat"` from `s`.
* (c)aa(at)
* (c)a(a)a(t)
* (ca)aa(t)
### Example 2:
```java
Input: s = "xxyxy", t = "xy"
Output: 5
```
Explanation: There are 5 ways you can generate `"xy"` from `s`.
* (x)x(y)xy
* (x)xyx(y)
* x(x)(y)xy
* x(x)yx(y)
* xxy(x)(y)
### Constraints
* `1 <= s.length, t.length <= 1000`
* `s` and `t` consist of English letters.
### Solution
類似 Longest Common Subsequence 的概念。將字串 s 與字串 t 逐一比較:
* 若某字元配對成功，則兩者同時往前推進
* if `s[i] = t[j]` then `s[i+1] and t[j+1]`
* 若某字元配對失敗，則只有字串 s 往前推進
* else `s[i+1]`
* 配對成功時，因為後面可能會有重複字元出現，所以也可以選擇只推進字串 `s`
* 配對到底後，若字串 `t` 為空字串，表示 subsequence 配對成功，回傳一次
```python=
class Solution:
def numDistinct(self, s: str, t: str) -> int:
M = [[-1 for _ in range(len(t))] for _ in range(len(s))]
def dp(i, j):
if j == len(t):
return 1
if i == len(s):
return 0
if M[i][j] != -1:
return M[i][j]
if s[i] == t[j]:
M[i][j] = dp(i + 1, j + 1) + dp(i + 1, j)
else:
M[i][j] = dp(i + 1, j)
return M[i][j]
return dp(0, 0)
```
### Complexity
* Time complexity: $O(m \times n)$
* m is the length of s
* n is the length of t
* Space complexity: $O(m \times n)$
## 9. Edit Distance
<font color="#ffbb00">**Medium**</font>
> You are given two strings `word1` and `word2`, each consisting of lowercase English letters.
>
> You are allowed to perform three operations on `word1` an unlimited number of times:
>
> * Insert a character at any position
> * Delete a character at any position
> * Replace a character at any position
>
> Return the minimum number of operations to make `word1` equal `word2`.
### Example 1:
```java
Input: word1 = "monkeys", word2 = "money"
Output: 2
```
Explanation:
`monkeys` -> `monkey` (remove `s`)
`monkey` -> `monkey` (remove `k`)
### Example 2:
```java
Input: word1 = "neatcdee", word2 = "neetcode"
Output: 3
```
Explanation:
`neatcdee` -> `neetcdee` (replace `a` with `e`)
`neetcdee` -> `neetcde` (remove last `e`)
`neetcde` -> `neetcode` (insert `o`)
### Constraints
* `0 <= word1.length, word2.length <= 100`
* `word1` and `word2` consist of lowercase English letters.
### Solution
#### 1. Recursion ver.
(1) Base condition
* 當 `word1 = ""` 且 `word2 = "acde"`
* 此時 `word1` 需要操作 4 次的 insert
* 當 `word1 = "abc"` 且 `word2 = ""`
* 此時 `word1` 需要操作 3 次的 delete
綜上所述，當某一個字串長度 = 0 時，操作次數 = 另一個非空字串的長度
(2) 類似 Longest Common Subsequence(LCS)
兩個字串逐一比較字元，
* 當字元相同時，兩者往前推進一位
* if `w1[i] = w2[j]` then (i+1, j+1)
* 當字元不同時，有三種操作
* insert: (i, j+1)
* 在 `word1` 強制插入與 `word2` 相同的字元，使得 `word2` 推進但 `word1` 不動
* remove: (i+1, j)
* 在 `word1` 強制移除不同的字元，使得 `word1` 推進但 `word2` 不動
* replace: (i+1, j+1)
* 強制在 `word1` 中替換一個與 `word2` 相同的字元，使得兩者都推進
* 三種操作中選一個操作次數最少的
```python=
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
m = len(word1)
n = len(word2)
M = [[-1 for _ in range(n)] for _ in range(m)]
def dp(i, j):
if i == m:
return n - j
if j == n:
return m - i
if M[i][j] != -1:
return M[i][j]
if word1[i] == word2[j]:
M[i][j] = dp(i+1, j+1)
else:
M[i][j] = 1 + min(dp(i, j+1), dp(i+1, j), dp(i+1, j+1))
return M[i][j]
return dp(0, 0)
```
#### 2. Iteration ver.
在表格中，三種操作剛好對應 cell 往三個方向(右/下/對角)移動。往每一個 cell 的最小操作次數受到兩個影響:
* 對應字串相同，直接看對角線的前一步驟的最小值
* 對應字串不同，取三個方向的最小值，再 + 上 cell 本身的一次操作
```python=
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
m, n = len(word1), len(word2)
M = [[-1 for _ in range(n + 1)] for _ in range(m + 1)]
# boundary
for i in range(m + 1):
M[i][n] = m - i
for j in range(n + 1):
M[m][j] = n - j
for i in range(m - 1, -1, -1):
for j in range(n - 1, -1, -1):
if word1[i] == word2[j]:
M[i][j] = M[i+1][j+1]
else:
M[i][j] = 1 + min(M[i+1][j], M[i][j+1], M[i+1][j+1])
return M[0][0]
```
### Complexity
* Time complexity: $O(m \times n)$
* m is the length of word1
* n is the length of word2
* Space complexity: $O(m \times n)$
## 10. Burst Balloons
<font color="#ee2f56">**Hard**</font>
> You are given an array of integers `nums` of size `n`. The `ith` element represents a balloon with an integer value of `nums[i]`. You must burst all of the balloons.
>
> If you burst the `ith` balloon, you will receive `nums[i - 1] * nums[i] * nums[i + 1]` coins. If `i - 1` or `i + 1` goes out of bounds of the array, then assume the out of bounds value is 1.
>
> Return the maximum number of coins you can receive by bursting all of the balloons.
### Example 1:
```java
Input: nums = [4,2,3,7]
Output: 167
Explanation:
nums = [4,2,3,7] --> [4,3,7] --> [4,7] --> [7] --> []
coins = 4*2*3 + 4*3*7 + 1*4*7 + 1*7*1 = 143
```
### Constraints
* `n == nums.length`
* `1 <= n <= 300`
* `0 <= nums[i] <= 100`
### Recommended complexity
* Time complexity: $O(n^3)$
* Space complexity: $O(n^2)$
### Solution
(1) subproblem 的選擇(False)
不能將 array 分解。以 Example 1 的 `nums = [4, 2, 3, 7]` 為例，當選擇爆破 `nums[2] = 3` 後可將原始陣列分為 `leftArray = [4, 2]` 與 `rightArray = [7]`。而 `leftArray = [4, 2]` 中可以再選擇 2，可得 `coins = 4 * 2 * 1`。
但實際上 `leftArray` 與 `rightArray` 應該是要合併的，選擇 2 的結果應該是 `4 * 2 * 8` 才對。
(2) subproblem 的選擇(True)
反過來思考，如果選擇的數字不是先刪除而是最後刪除。同樣以 Example 1 的 `nums = [4, 2, 3, 7]` 為例，若選擇 `nums[2] = 3` 為最後刪除，則對 3 而言的 `coins = 1 * 3 * 1`。它的前一步(subproblem)是 `leftArray = [4, 2]` 和 `rightArray = [7]`，且兩者不為有合併的問題(因為 `nums[2] = 3` 可作為兩者分界)。
<img src="https://hackmd.io/_uploads/HkcXJlCjkl.jpg" width=300>
因此，可先將 `nums = [4, 2, 3, 7]` 擴充為 `nums = [1, 4, 2, 3, 7, 1]`。假設 `nums[2] = 2` 為最後刪除，則它的貢獻以及子問題為:
`nums[L-1] * 2 * nums[R+1] + dp[L][i-1] + dp[i+1][R]`。
<img src="https://hackmd.io/_uploads/B1DN1x0s1l.jpg" width=600>
依此類推，每次迭代 subproblem 中的所有元素作為可能被最後刪除的元素，再取最大值。
```python=
class Solution:
def maxCoins(self, nums: List[int]) -> int:
nums = [1] + nums + [1]
M = [[-1 for _ in range(len(nums))] for _ in range(len(nums))]
def dp(L, R):
if L > R:
return 0
if M[L][R] != -1:
return M[L][R]
res = 0
for i in range(L, R + 1):
coins = nums[L-1] * nums[i] * nums[R+1] + \
dp(L, i - 1) + \
dp(i + 1, R)
res = max(res, coins)
M[L][R] = res
return M[L][R]
return dp(1, len(nums) - 2)
```
## 11. Regular Expression Matching
<font color="#ee2f56">**Hard**</font>
> You are given an input string `s` consisting of lowercase english letters, and a pattern `p` consisting of lowercase english letters, as well as `'.'`, and `'*'` characters.
>
> Return `true` if the pattern matches the **entire** input string, otherwise return `false`.
>
> * `'.'` Matches any single character
> * `'*'` Matches zero or more of the preceding element.
### Example 1:
```java
Input: s = "aa", p = ".b"
Output: false
```
Explanation: Regardless of which character we choose for the `'.'` in the pattern, we cannot match the second character in the input string.
### Example 2:
```java
Input: s = "nnn", p = "n*"
Output: true
```
Explanation: `'*'` means zero or more of the preceding element, `'n'`. We choose `'n'` to repeat three times.
### Example 3:
```java
Input: s = "xyz", p = ".*z"
Output: true
```
Explanation: The pattern `".*"` means zero or more of any character, so we choose `".."` to match `"xy"` and `"z"` to match `"z"`.
### Constraint
* `1 <= s.length <= 20`
* `1 <= p.length <= 20`
* Each appearance of `'*'`, will be preceded by a valid character or `'.'`.
### Recommended complexity
* Time complexity: as good or better than $O(m \cdot n)$
* m is the length of string s
* n is the length of string p
* Space complexity: as good or better than $O(m \cdot n)$
### Solution
由字串 `p` 去配對字串 `s`，記憶化陣列 `M[i][j]` 表示 `s[i:]` 與 `p[j:]` 是否匹配。每個位置會有以下三種配對狀況:
* 若 `p[j]` 是字母
* 若 `p[j] = s[i]`，則兩者都推進一位: `(i+1, j+1)`
* 若 `p[j] != s[i]`，則該位置不匹配: False
* 若 `p[j]` 是 `"."`: 同上第一個，兩者推進一位 `(i+1, j+1)`
* 若 `p[j]` 是 `"*"` 有兩種選擇(注意 `"*"` 不能單獨存在，要與前面的字元一起作用)
* 不重複前一個，只推進 p: `(i, j+2)`
* 重複前面的，但前提是前一個要配對成功，因為如果前一個配對失敗那重複也沒意義: `(i+1, j)`
可繪製樹狀圖如下
Base condition:
* 如果最後 `i >= len(s)` 且 `j >= len(p)` 表示字串 `s` 與 `p` 走完: `True`
* 如果 `j >= len(p)` 表示 s 還沒匹配完就結束: `False`
* 如果 `i >= len(s)` 表示 `s` 配對完: `True`
```python=
class Solution:
def isMatch(self, s: str, p: str) -> bool:
M = {}
def dp(i, j):
if i >= len(s) and j >= len(p):
return True
if (i, j) in M:
return M[(i, j)]
if j >= len(p):
return False
match = i < len(s) and (s[i] == p[j] or p[j] == '.')
if (j + 1) < len(p) and p[j+1] == '*':
M[(i, j)] = dp(i, j + 2) or (match and dp(i + 1, j))
return M[(i, j)]
if match:
M[(i, j)] = dp(i+1, j+1)
return M[(i, j)]
M[(i, j)] = False
return M[(i, j)]
return dp(0, 0)
```
Sign in with Wallet
Connect another wallet