# Python-LeetCode 581 第15招 Dynamic Programming II：二維
## 二維的例題
[(題目連結) 63. Unique Paths II (Medium)](https://leetcode.com/problems/unique-paths-ii/)
從方格圖的左上角要走到右下角，每一步只能往下或是往右一格，但有些格子(0)可以走，有些(1)不能走，請問有多少種不同的路徑數。
只能往下以及往右，所以可以看成是一個DAG，由上而下由左而右就是一個topological sort。若$dp[i][j]$是走到$(i,j)$的路徑數，首先，若$grid[i][j]=0$(不可通行)，則$dp[i][j]=0$；否則，在可以通行的狀況下，因為前一步一定是$(i-1,j)$或$(i,j-1)$，所以
$dp[i][j]=dp[i-1][j]+dp[i][j-1]$ for $i>0,j>0$ (if $grid[i][j]=0$)；
邊界條件是
$dp[i][0]=dp[i-1][0]$ for $i>0$；
$dp[0][j]=dp[0][j-1]$ for $j>0$；以及
$dp[0][0]=1$。
計算順序就逐列逐行就可以，以下是範例程式。因為每個格子的內容在算完$dp$後就沒用了，我們直接將$dp$值寫在原陣列$grid$中。時間複雜度$O(mn)$，因為有$mn$個格子，每個格子花$O(1)$。
```python=
class Solution:
def uniquePathsWithObstacles(self, grid: List[List[int]]) -> int:
m = len(grid)
n = len(grid[0])
if grid[0][0] or grid[m-1][n-1]:
return 0
grid[0][0] = 1
for j in range(1,n):
if grid[0][j]:
grid[0][j] = 0
else:
grid[0][j] = grid[0][j-1]
for i in range(1,m):
if grid[i][0]:
grid[i][0] = 0
else:
grid[i][0] = grid[i-1][0]
for i in range(1,m):
for j in range(1,n):
if grid[i][j]: #obstacle
grid[i][j] = 0
else:
grid[i][j] = grid[i-1][j]+grid[i][j-1]
return grid[m-1][n-1]
```
[(題目連結) 64. Minimum Path Sum (Medium)](https://leetcode.com/problems/minimum-path-sum/)
題目說給一個方格圖，每個格子有一個非負整數，每一步只能往下或是往右一格，要找出左上角要走到右下角的路徑所經過的數字總和最小值。
與前題十分類似。令$dp[i][j]$是走到$(i,j)$的最小值，因為前一步一定是$(i-1,j)$或$(i,j-1)$，所以
$dp[i][j]=\min(dp[i-1][j],dp[i][j-1])+grid[i][j]$。
邊界條件是第0列與第0行。這題也可以逐列逐行計算，我們拿它來示範一下top-down memoization且使用Python提供的函數快取。
以下是範例程式。第4 ~ 9行我們寫一個函數$dp(i,j)$計算並回傳所要計算的DP值，注意到第4行在def之前我們加上了decorator
"@lru_cache(maxsize=None)"。
這會讓系統幫我們做memoization的動作。這個函數是一個直接根據遞迴式寫的遞迴函數，第6 ~ 8行是邊界條件。
時間複雜度$O(mn)$，有$mn$個格子，每個格子花$O(1)$，因為有memoization所以每個格子雖然會被呼叫兩次，但只會進入遞迴一次，第二次被呼叫時，就會直接回傳前一次算過的結果，不會重複遞迴。
```python=
class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
m,n = len(grid), len(grid[0])
@lru_cache(maxsize=None)
def dp(i,j):
if i==0 and j==0: return grid[0][0]
if i==0: return dp(i,j-1)+grid[i][j]
if j==0: return dp(i-1,j)+grid[i][j]
return min(dp(i-1,j), dp(i,j-1))+grid[i][j]
return dp(m-1,n-1)
```
再看一題方格圖的問題。
[(題目連結) 2304. Minimum Path Cost in a Grid (Medium)](https://leetcode.com/problems/minimum-path-cost-in-a-grid/description/)
題目說有一個$m\times n$的方格圖(grid, matrix)，每一個的數字恰好是0 ~ $mn-1$各出現一次。現在要從最上方的一列中的任何格子出發，每一步可以走到下一列的任何一個位置，直到最後一列。要找出成本最小的路徑，其中路徑成本的計算方式為路徑所經過的數字總和加上每一步的移動成本，而從格子數字$i$移動到下一列第$j$行的一步移動成本是$moveCost[i][j]$，這是輸入中給定的。
一列一列往下移，很自然的DP。我們一列一列的計算，對於每一列，計算停在該列每一個格子的最小成本就可以了。根據題目的說明，計算$dp[i][j]$時，考慮從上一列的每個點走過來的最小成本：
$$
dp[i][j] = \min_{0\leq k<n}\{dp[i-1][k] + moveCost[grid[i-1][k]][j]\}
$$
以下是範例程式。因為每次計算一列，用一個list $d$記錄前一列的每一個格子成本，初始最上面一列時就是格子內的數字(第4行)。接著跑迴圈一列一列往下算，我們用list comprehension的方式一行就直接做出下一列，所以就直接放回$d$就好了，不必再另取名字。
時間複雜度$O(mn^2)$。
```python=
class Solution:
def minPathCost(self, grid: List[List[int]], moveCost: List[List[int]]) -> int:
m,n = len(grid),len(grid[0])
d = grid[0]
for i in range(1,m):
d = [grid[i][j]+min(d[k]+moveCost[grid[i-1][k]][j]
for k in range(n)) for j in range(n)]
#
return min(d)
```
接著看很有名的背包問題。
**0/1-Knapsack problem(背包問題)**
有一些物品，每個物品有重量與利益，今有一個背包的重量限制，要在物品中挑選總重量不超過重量限制下的最大利益總和。這是所謂背包問題，"0/1"的意思是物品只能挑選或不挑選，不可切割。
若物品可以切割後選取任意比例，稱為fractional knapsack problem，可以用貪心法則來求得最佳解(CP值高的先選)。0/1-背包問題是NP-hard，目前找不到多項式時間複雜度的有效率解法。
0/1-knapsack有兩個解法，當物品個數$n$不大時，我們可以枚舉所有子集合，因為子集合的數量是$2^n$，利用遞迴暴搜，通常時間複雜度是$O(2^n)$。
當$n$太大時，我們難以枚舉所有子集合，但其實我們要的不是所有子集合，而是**所有子集合的個別總和**。當物品的重量不大時，例如總和為$W$，雖然子集合個數很多，但子集合的和卻不會太多種：0到$W$之間的所有整數，最多不超過$W+1$種。這個想法導致以下的DP算法。
從DP的角度來解背包問題時，若定義子問題為：$dp[i]$是前$i$種種物品構成的最佳解，則難以找到$dp[i]$的遞迴關係式，因為缺乏optimal substructure的特性。我們因此進一步切割子問題，也就是多加入一個重量的維度：定義$dp[i][w]$是前$i$種物品且重量為$w$的最佳解，則可以找到遞迴關係式，考慮納入第$i$項物品與否的兩種情形：
$$
dp[i][w] = \max\Bigg\{
\begin{array}{l}
dp[i-1][w-weight[i]]+p[i]\\
dp[i-1][w]
\end{array}
\Bigg\}
$$
for $w\geq weight[i]$，其中$weight[i]$與$p[i]$是第$i$物品的重量與利益。
這就導致了一個二維的DP，表格大小是$nW$，時間複雜度$O(nW))$，其中$W$是重量限制，以此法來解時，$W$的值不可太大，此導致的時間複雜度稱為**pseudo-polynomial**。此外我們可以注意到每一列都只與前一列有關，因此可以用滾動陣列的方式將二維表格簡化為兩個一維陣列(list)，有些題目甚至可以用一個list就可以做。
註：若題目的重量範圍很大，但利益值是很小的範圍的時候，我們也可用獲得的利益將做DP的參數。
以下我們將看幾個例題。
[(題目連結) 322. Coin Change (Medium)](https://leetcode.com/problems/coin-change/description/)
換銅板的問題是背包問題的一種經典形式。本題說有一些不同銅板的面額，要用最少的銅板讓總值加起來恰好是某個數。
與基本背包問題的差別是每個面額的銅板有無限多個可以使用。雖然如此，但DP的精神沒有太大差別。
令$dp[i][w]$是前$i$種銅板組成總額$w$的最佳解(最少銅板數量)，考慮第$i$個銅板使用了$0,1,2,\ldots$等各種可能的最佳解，
$$
dp[i][w]=\min_{0\leq j\leq w/coin[i]}\Bigg\{dp[i-1][w-j\times coin[i]]+j\Bigg\}
$$
如果直接照這個遞迴式做，每一個表格位置$dp[i][w]$還需要一個迴圈，這個將導致時間複雜度比較差。考慮到**用了$j$枚$coin[i]$等同用了$j-1$枚之後再用一枚**，假設我們$w$從小算到大，
$dp[i][w]=\min\{dp[i-1][w], dp[i][w-coin[i]]+1\}$。
從實質意義去看，當我們算到$dp[i][w]$時，$dp[i][w-coin[i]]$已經涵蓋了用了$\leq i$的各種硬幣的最佳解，所以只要考慮再加一枚$coin[i]$就好。
根據這個遞迴式來做就簡單了，神奇的是我們只要使用一個一維陣列就可以了。以下是範例程式。時間複雜度$O(nW)$，$W$是總額範圍。
註：很多演算法都有這樣的場景：我們在一個回合中，要從某些現有資料計算出來結果，並將該結果當做下一回合的現有資料。
假設我們將資料放在某容器$D$，此時，我們應該避免在一個回合進行中，將計算出來的值直接存回$D$，因為這會導致在**歷遍容器過程中改變容器內容**。這往往是初學者容易犯的錯誤，但本題恰好可以錯打正著。當然，我們是知道可以這麼做是對的時候，才可以這麼做。
```python=
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
oo = 10001
dp = [0]+[oo]*amount
for v in coins:
for i in range(amount-v+1):
if dp[i]+1 < dp[i+v]:
dp[i+v] = dp[i]+1
#
if dp[-1] == oo: return -1
return dp[-1]
```
[(題目連結) 416. Partition Equal Subset Sum (Medium)](https://leetcode.com/problems/partition-equal-subset-sum/)
給一個正整數的陣列，請問是否可以將其中的成員分成兩個子集使得兩個子集的總和相等。這裡的子集是指multi-set，也就是允許相同元素出現多次，陣列長度不超過200，陣列內容不超過100。
本題是以下更一般化的題目的特例：給一群數字，請問是否有一個子集的總和為$K$？或者找最接近$K$的總和，其中接近也可以定義為不超過或不小於。
這些題目的做法都一樣。因為基本上我們會找出所有子集合的總和。這其實是背包問題的退化形式，也就是當每個物品的重量等於利益時，可否裝到某個重量的問題。
就本題來說，我們先算出所有數字總和，總和的一半就是想要的目標，如果有一個子集合是總和的一半，那剩下的總和一定也是總和的一半。
以下是範例程式。先算出總和$total$，第4行特判掉兩個不可能的情況，然後算出要找的總和目標$target$。
我們將歷遍每一個陣列中的數字，維護好目前為止哪些總和是湊得出來的。
第6行的$dp$就是來記錄此資訊，$dp[i]=True$若且惟若目前存在子集合的總和為$i$，初始時，只有$0$是可以被湊出來的。
第7行開始歷遍每一個陣列數字$v$，這裡我們用了一個技巧來省記憶體，我們由後往前檢查可能的總和$i$，若$i$之前是可以湊得出來，那麼配上現在的$v$就可以湊出$i+v$。因為這一題的數字都是正整數，所以由大往小做，新改變的結果不會在歷遍$i$的過程被踩到，所以答案是對的。時間複雜度$O(n)$。
當然，用二維陣列來做或滾動陣列來做也是可以的。
```python=
class Solution:
def canPartition(self, nums: List[int]) -> bool:
n,total = len(nums),sum(nums)
if total&1 or n==1: return False
target = total >>1
dp = [True] + [False]*target
for v in nums:
if v > target: return False
for i in range(target-v, -1, -1):
if dp[i]: dp[i+v] = True
return dp[target]
```
這一題用set()來做速度更快。將可以組成的數字放在一個集合$d$中，一個考慮一個成員$v$，將可以組成的數字加上$v$也是可以組成的數字，新算出的數字加入$d$。重點是重複的不要重複存，以及超出目標的不要留存。
```python=
class Solution:
def canPartition(self, nums: List[int]) -> bool:
n,total = len(nums),sum(nums)
if total&1 or n==1: return False
target = total >>1
# using set
d = {0}
for v in nums:
d |= {p+v for p in d if p<=target-v}
if target in d: return True
return False
```
接著看一個難度Hard的題目。
[(題目連結) 2742. Painting the Walls (Hard)](https://leetcode.com/problems/painting-the-walls/)
題目說有$n$面牆要粉刷，有一位需要付費的油漆匠，粉刷第$i$面牆需要花$time[i]$的時間並且收費$cost[i]$。另外有一位免費的油漆匠，每一單位時間可以刷好任何一面牆，而且不收費，但必須在收費油漆匠工作期間才能請免費油漆匠粉刷。你的問題是要找出最少的總成本把全部的牆粉刷完畢。也就是說要找出其中某些牆$S$請收費油漆匠粉刷，剩下的請免費油漆匠刷。假設收費油漆匠這些牆需要的時間是$time(S)$，那麼根據規則，免費的最多只能有$time(S)$面牆，因此，必須滿足$time(S)+|S|\geq n$。答案就是滿足條件的成本總和最小的子集合。
對於任何第$i$面牆，把$time[i]+1$看成利益，$cost[i]$當重量，就是找利益至少$n$的最小成本子集合，就是個0/1-背包問題。此處利益值是一個小範圍的整數，是我們要DP的對象。
為了方便，我們用$dp[i]$表示**利益小於等於$i$的最小成本**，這樣$dp$會是個非遞減序列。將每一面牆逐步納入考量，根據挑選或不挑選這面牆，更新整個$dp$的每一個可能值。
以下是範例程式，實作時注意以下細節，
* 因為是要找條件$\geq n$的，但是我們只存$\leq n$的，太大的不需要存(要存也會有麻煩)，所以我們使用一個變數$opt$存目前的最佳解，超過滿足條件的直接納入目前最佳解$opt$。
* 如果$time[i]+1\geq n$，也就是單選這一個就夠了，就直接看看要不要更新$opt$就好。
* 由後往前做，可以只用一個list。
* 留意邊界條件，不要踩到$dp[<0]$。
時間複雜度$O(n^2)$。
```python=
class Solution:
# min cost subset S of time(S)+|S| >=n
def paintWalls(self, cost: List[int], time: List[int]) -> int:
n = len(cost)
oo = 10**9
dp = [0]+[oo]*n
opt = oo
for c,t in zip(cost,time):
if t+1 >= n:
opt = min(opt,c)
continue
opt = min(opt,c+dp[n-t-1])
for i in range(n-t-2,-1,-1):
dp[i+t+1] = min(dp[i]+c,dp[i+t+1])
for i in range(1,t+1):
dp[i] = min(dp[i],c)
#
return opt
```
**Longest Common Subsequence (LCS)**
[(題目連結) 1143. Longest Common Subsequence (Medium)](https://leetcode.com/problems/longest-common-subsequence/)
給兩個字串，求Longest Common Subsequence的長度。子序列是指在原序列中取出某些位置的成員但不變動其順序所得的序列，或者也可以說是在一個序列中刪除某些成員後剩下的結果。
LCS是個經典的問題，也是二維DP的常見教學題。假設輸入字串是$S1$與$S2$，子問題的定義為：令$lcs[i][j]$是$S1[:i+1]$與$S2[:j+1]$的LCS長度，也就是$S1$的前面$i$個與$S2$的前面$j$個的最佳解。我們分兩個情形：
* 如果$S1[i]\neq S2[j]$：既然兩者不相等，兩者中至少有一個對找LCS是沒有幫助的，也就是說，我可以刪掉$S1$的最後一個字母$S1[i]$或者刪掉$S2[j]$，因為要找越長越好的，所以兩者取其大， $lcs[i][j]=\max(lcs[i-1][j], lcs[i][j-1])$。
* 如果$S1[i]=S2[j]$：因為我們只計算LCS的長度，跟在哪個位置對中無關，所以既然對中，不對白不對，把其中一個刪除不會更好，因此可以得到 $lcs[i][j]=lcs[i-1][j-1]+1$。
邊界條件是其中若有一個字串長度為0時，其LCS當然為0，最後的答案在$lcs[m-1][n-1]$，$m,n$分別為兩字串的長度。
觀察一下遞迴式，每一個狀態只與其左方、上方、以及左上方有關，所以我們可以逐列逐行的計算就是一個合法的順序，而且只需要保留前一列就可以，所以可以用滾動陣列來節省記憶體與時間。
以下是範例程式。啟用兩個list：前一列放在$d$，目前列放在$p$，每次都由$d$算到$p$，再將兩者交換。時間複雜度$O(mn)$，因為有$mn$個格子要算，每個格子只需$O(1)$。
```python=
class Solution:
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
m,n = len(text1),len(text2)
d,p = [0]*n,[0]*n
for ch in text1:
p[0] = 1 if ch==text2[0] else d[0]
for i in range(1,n):
if ch == text2[i]:
p[i] = d[i-1]+1
else: p[i] = max(p[i-1],d[i])
d,p = p,d
return d[-1]
```
[(題目連結) 115. Distinct Subsequences (Hard)](https://leetcode.com/problems/distinct-subsequences/)
給兩個字串$s$與$t$，求$s$中有幾個subsequence等於$t$。
令$dp[i][j]$為$s[:i]$中等於$t[:j]$的subsequence數量，其中$s[:i]$是不含$s[i]$的$s$前綴(Python的寫法)。這是為了表達初始空字串的狀況，對於所有$i$，$dp[i][0]=1$因為$t[:0]$是空字串。
* 若$s[i]\neq t[j]$，$s[i]$的加入對$dp[i+1][j+1]$並無幫助，因此$dp[i+1][j+1]=dp[i][j+1]$
* 否則，$s[i]= t[j]$，$dp[i+1][j+1] = dp[i][j]+dp[i][j+1]$，其中使用$s[i]$去配對$t[j]$有$dp[i][j]$個，而不使用$s[i]$的有$dp[i][j+1]$個。
最後的答案在$dp[m][n]$，其中$m,n$分別是$s,t$的長度。觀察遞迴式可以簡單知道，逐列逐行計算就可以，而且每一列只與前一列有關，所以可以用滾動陣列的方式。
以下是範例程式，與前題一樣，我們把前一列放在$d$，目前列放在$p$，每次都由$d$算到$p$，再將兩者交換。時間複雜度$O(mn)$，因為有$mn$個格子要算，每個格子只需$O(1)$。
```python=
class Solution:
# dp[i][j] = num of subsequence(s[:i]) = t[:j]
# dp[i+1][j+1] = dp[i][j]+dp[i][j+1] if s[i]==t[j]
# = dp[i][j+1] otherwise
# initial null subsequence = 1
def numDistinct(self, s: str, t: str) -> int:
m,n = len(s), len(t)
d = [0]*(n+1)
d[0] = 1
for ch in s:
p = [1]+[0]*n
for j in range(n):
if ch == t[j]:
p[j+1] = d[j]+d[j+1]
else:
p[j+1] = d[j+1]
d,p = p,d
#
return d[n]
```
[(題目連結) 221. Maximal Square (Medium)](https://leetcode.com/problems/maximal-square/)
在一個0/1矩陣中找出最大全部都是1的方陣。
令$dp[i][j]$是以$(i,j)$為右下角的最大方陣的邊長。如果$matrix[i][j]$是0，那當然沒有方陣，也就是邊長為0；如果$matrix[i][j]$是1，如下圖所示，若以$(i,j)$為右下角的正方形邊長為$k$，則以$(i-1,j)$、$(i,j-1)$與$(i-1,j-1)$為右下角的三個正方形邊長都至少必須是$k-1$。因此，
$dp[i][j]=\min\{dp[i-1][j], dp[i][j-1],dp[i-1][j-1]\}+1$。
以下是範例程式，計算順序仍然是逐列逐行，我們直接將DP的值存在輸入的陣列中，此外，留意本題輸入的是字串。時間複雜度$O(mn)$。
```python=
class Solution:
def maximalSquare(self, matrix: List[List[str]]) -> int:
# dp[i][j] = largest side of square with right-bottom at (i,j)
m,n = len(matrix),len(matrix[0])
for i in range(m):
for j in range(n):
matrix[i][j] = int(matrix[i][j])
if i==0 or j==0 or matrix[i][j] == 0: continue
matrix[i][j] = min(matrix[i-1][j],matrix[i][j-1],
matrix[i-1][j-1])+1
#end for
k = max(max(row) for row in matrix)
return k*k
```
[(題目連結) 920. Number of Music Playlists (Hard)](https://leetcode.com/problems/number-of-music-playlists/)
有$n$首不同的歌，要建立一個$goal$首歌的播放清單，條件是(1).每首歌至少要出現一次；(2).同一首歌之間至少需要間隔$k$首歌。請問有多少種可能的播放清單。輸入$0\leq k<n\leq goal$。
首先，我們先固定一個歌的編號，最後答案再乘上$n!$，因為任何一個清單都可以有$n!$的排列變化。
令$dp[n][m]$是包含了$n$首不同歌，長度為$m$的清單數。我們有以下遞迴式：
$dp(n,m) = dp(n-1,m-1)+dp(n,m-1)*(n-k)$，其中$dp(n-1,m-1)$對應最後一首是第$n$首第一次出現；而$dp(n,m-1)*(n-k)$是最後一首在前面有出現過，請注意，最後的$k$首歌必然都是不一樣的歌，所以最後一首有$n-k$種可能選擇。
初始條件是：
* 若$m<n$，$dp(n,m)=0$，因為總歌曲數不可能小於歌曲種類。
* 當$n=m$時，沒有重複的歌，$dp(n,n)=1$，因為我們固定了歌的編號排列。
* 當$n=k+1$時，因為必須間隔$k$個才能重複，因此前$n$個不能重複，而下一個只能重頭循環，結論是只能有一種排列。例如$k=3$而$n=4$時，唯一的排列就是$(1,2,3,4,1,2,3,4,\ldots)$。所以，$dp(n=k+1,m>=n)=1$。而$n\leq k$的dp值不需計算。
每一格只需要左上方我上方的值，所以從第$k+2$列開始，逐列逐行計算即可，以下是範例程式。時間複雜度$O(mn)$。
```python=
class Solution:
# first fix a perm 12345..., then *n!
# length=m, dp(n,m) = dp(n-1,m-1)+dp(n,m-1)*(n-k);
# dp(n,m<n)=0, dp(n,n)=1, dp(n=k+1,m>=n)=1
def numMusicPlaylists(self, n: int, goal: int, k: int) -> int:
mod = 1000000007
dp = [[0]*(goal+1) for i in range(n+1)]
for i in range(1,n+1): dp[i][i] = 1
for i in range(k+1,goal+1):
dp[k+1][i] = 1
for i in range(k+2,n+1):
for j in range(i+1,goal+1):
dp[i][j] = (dp[i-1][j-1]+dp[i][j-1]*(i-k))%mod
return (dp[n][goal]*perm(n))%mod
```
### 2D1D DP
2D1D的DP常見的形式是要求的子問題(狀態)是序列的某些區間 $[i,j]$，其遞迴式形如
$$
dp(i,j) =\min_{i<k<j}f(dp(i,k), dp(k,j))
$$
全部有$O(n^2)$個狀態，也就是區間數量，而每一個狀態需要$O(n)$個前置狀態。2D1D的DP用Top-down memoization是比較合適的。
教科書上常見的經典題包含切棍子、矩陣乘法鏈、以及Optimal Binary Search Tree。以下是LeetCode上切棍子的題目。
[(題目連結) 1547. Minimum Cost to Cut a Stick (Hard)](https://leetcode.com/problems/minimum-cost-to-cut-a-stick/description/)
有一根棍子，上面標示了若干個切割點，你需要以每次切一個的方式把這些切割點切割開，每一次切割的成本是該次切割時棍子的長度。你的問題是要找一個切割的順序使得總切割成本最小。
切割點的位置是與左端的距離，都是整數。下圖是一個例子，切割點是$[3,5,1,4]$，如果依照$3\rightarrow 5 \rightarrow 1\rightarrow 4$的順序切割，第一次的長度是7，第二次切割時所需切割的棍子長度是$7-4=3$，第三次切割時，成本是$3-0=3$，第四次成本是$2$，總成本是$7+4+3+2=16$，這是本例最小的成本。
我們不知道切割的順序，但總有第一刀，而且第一刀必是這些切割點其中之一(好個廢話)，既然不知道第一刀在哪裡，我們就嘗試所有可能的第一刀。
首先將切割點排序，為了方便起見，我們將左端(座標0)與右端(座標$n$)也納入，$cuts[i]$是排序後第$i$點的座標。定義$dp(i,j)$是第$i$個切割點到第$j$個切割點這一段棍子需要被切割的最小總成本。我們要求的是$dp(0,m-1)$，其中$m$是切割點的數目(包含左右端點)。
當$j=i+1$時，$dp(i,j)=0$，因為相鄰兩切割點之間沒有切割點；對於$j>i+i$，我們嘗試其中的任一點$k$當做第一刀，當第一刀切完之後，棍子斷成兩段，兩邊的最小成本加上第一刀的成本就是這一段的成本，我們要求最小，所以
$$
dp(i,j)=\min_{i<k<j}\{dp(i,k)+dp(k,j)\}+cuts[j]-cuts[i]
$$
DP不是很簡單嗎！時間複雜度是多少？如果跑純遞迴會很糟糕，但DP的話所有的狀態就只有$O(m^2)$種，因為$0\leq i<j<m$，每一種需要一個迴圈不超過$O(m)$，所以最多$O(m^3)$。
這題我們示範top-down的寫法，以下是利用Python自動的memoization的範例程式。基本上就照遞迴式寫就好了，留意第5行函數定義前一行的lru_cache()。
```python=
class Solution:
def minCost(self, n: int, cuts: List[int]) -> int:
cuts = sorted([0,n]+cuts)
m = len(cuts)
@lru_cache(maxsize=None)
def dp(i,j):
if j<=i+1: return 0
imin = dp(i+1,j)
for k in range(i+2,j):
imin = min(imin, dp(i,k)+dp(k,j))
return imin+cuts[j]-cuts[i]
return dp(0,m-1)
```
自己寫memo也沒有複雜很多，以下是範例程式。
```python=
class Solution:
def minCost(self, n: int, cuts: List[int]) -> int:
cuts = sorted([0,n]+cuts)
m = len(cuts)
d = [[-1]*m for i in range(m)]
def dp(i,j):
if j<=i+1: return 0
if d[i][j]>=0: return d[i][j]
imin = dp(i+1,j)
for k in range(i+2,j):
imin = min(imin, dp(i,k)+dp(k,j))
d[i][j] = imin+cuts[j]-cuts[i]
return d[i][j]
return dp(0,m-1)
```
[(題目連結) 87. Scramble String (Hard)](https://leetcode.com/problems/scramble-string/description/)
題目描述了一個把字串攪亂的隨機方法：
* 如果長度為$1$就停止；
* 如果長度$>1$，依下列步驟
* 隨機挑選一個位置，將字串切成左右兩段非空字串
* 隨機決定是否交換兩子字串
* 遞迴操作這兩段子字串
現在給你兩段長度相同的字串$s1$與$s2$，請問$s2$是否是$s1$經過上述程序產生的。
使用DP的想法來做。令$dp(l1,r1,l2,r2)$是對於字串$s1[l1:r1]$與$s2[l2:r2]$的答案，也就是其中之一是否是另外一個的scrambled string。
先檢查兩個字串都個字排序後是否一樣，如果不一樣就是False。如果排序後相同，需要進一步檢查，長度若不超過2則答案一定是True。
否則，我們根據題目的操作來寫，嘗試在每一個可能的位置切開兩個字串(第10行)，遞迴比較兩者的左端與右端(第11行)，或者是交換其中一段的左右之後再比較(第13行)，如果可以比較成功就是True，否則答案為False。
時間複雜度$O(n^4\log n)$，$n$是輸入字串的長度。對於$n$種可能的長度$l$，$s1$與$s2$各有$n-l$條可能的子字串，因此有$(n-l)^2$種組合，每種組合需要$O(l\log l)$的時間，總共的時間複雜度就是$\sum_{l=1}^{n}(n-l)^2(l\log l)\in O(n^4\log n)$。
```python=
class Solution:
def isScramble(self, s1: str, s2: str) -> bool:
n = len(s1)
@lru_cache(maxsize=None)
def dp(l1,r1,l2,r2):
s,t = s1[l1:r1], s2[l2:r2]
if sorted(s)!=sorted(t): return False
if len(s) <=2: return True
for i in range(1,len(s)):
if dp(l1,l1+i,l2,l2+i) and dp(l1+i,r1,l2+i,r2):
return True
if dp(l1,l1+i,r2-i,r2) and dp(l1+i,r1,l2,r2-i):
return True
return False
#main
ans = dp(0,n,0,n)
return ans
```
[(題目連結) 664. Strange Printer (Hard)](https://leetcode.com/problems/strange-printer/)
題目說有一個奇怪的印表機，每一次動作可以印出連續一段的相同字元，而且可以覆蓋在已經印出的位置。給一個字串$s$，請問該印表機最少需要幾次動作可以印出該字串。
例如"aaabbb"需要2次：一次印3個a，第二次印3個b。又例如"aba"也是2次：第一次先印3個a，第二次在第二個a上覆寫1個b。
首先，我們可以先移除連續的相同字母，因為連續2個以上的相同字母顯然可以在同一個動作中被印出，所以跟1個字母是一樣的。例如aabbbaaacc，我們可以改成abac。
令$dp(i,j)$是$[i,j]$這個區段子字串需要的最少動作，我們來列DP式。考慮$s[i]$，
* $s[i]$可能單獨在一個動作被印出，也就是$dp(i,j)=1+dp(i+1,j)$；
* 若對於某個$i<k\leq j$，$s[i]=s[k]$，$s[i]$與$s[k]$可能在同一個動作中被印出，也就是$dp(i,j)=dp(i+1,k-1)+dp(k,j)$
對各種狀況取最小值就是答案。邊界條件是$dp(i,i)=1$，因為一個字元需要一個動作。
以下是範例程式，以top-down方式來寫，自己寫memo。第7 ~ 9行是移除連續相同的字元後把字串放在$ss$。第11 ~ 12行準備小抄以及設初始條件。第13 ~ 20行是根據遞迴式計算的函數。最後答案在$dp(0,n-1)$也就是整段字串。
時間複雜度$O(n^3)$。
```python=
class Solution:
# Dp for each [i,j].
# s[i] either printed itself or togather with s[k] if s[i]=s[k]
# d[i,j] = min(1+d[i+1,j], d[i+1,k-1]+d[k,j])
def strangePrinter(self, s: str) -> int:
# remove duplicate, aaa is same as a
ss = s[0]
for i in range(1,len(s)):
if s[i]!=s[i-1]: ss += s[i]
n = len(ss)
d = [[0]*n for i in range(n)]
for i in range(n): d[i][i]=1
def dp(i,j): # ans for [i,j]
if d[i][j]>0: return d[i][j]
p = 1+dp(i+1,j)
for k in range(i+1,j+1):
if ss[i]==ss[k]:
p = min(p, dp(i+1,k-1)+dp(k,j))
d[i][j] = p
return p
#main
return dp(0,n-1)
```
[(題目連結) 241. Different Ways to Add Parentheses (Medium)](https://leetcode.com/problems/different-ways-to-add-parentheses/)
給一個由加減乘法與整數構成的運算式，輸入的式子沒有任何括弧，請找出各種加括弧的方式所得出的計算值。
所謂各種加括弧的方式就是對應到哪一個運算是最後一個運算，最後一個運算的左邊與右邊都各自求出所有的可能，再組合左邊與右邊的所有組合。
令$value(i,j)$是子字串$expr[i:j]$的所有可能值：
* 若$expr[i:j]$中沒有運算只有一個數字，直接回傳該數字構成的列表。
* 否則，有運算子，則對字串中每一個運算子，
* 將字串切成左右，各自遞迴
* 對所有可能的左邊值與所有可能的右邊值，根據此運算子組合成一個可能的值。
以下是範例程式，使用top-down且自己寫memo的方式。第9 ~ 11行是只有一個數字的邊界條件，
第13行的迴圈找所有運算子的位置，第15 ~ 16行則遞迴呼叫左右邊。然後第17 ~ 18行的雙迴圈枚舉所有可能的配對。
```python=
class Solution:
def diffWaysToCompute(self, expr: str) -> List[int]:
# dp, split at each operator
# record result of all posiible substring
n = len(expr)
dp = [[[] for j in range(n+1)] for i in range(n+1)]
def value(i,j): # all values of expr[i:j]
if dp[i][j]: return dp[i][j]
if expr[i:j].isdigit(): # only one int
dp[i][j] = [int(expr[i:j])]
return dp[i][j]
result = []
for p in range(i,j):
if expr[p] not in "+-*": continue
left = value(i,p)
right = value(p+1,j)
for u in left:
for v in right:
if expr[p]=='+':
result.append(u+v)
elif expr[p]=='-':
result.append(u-v)
else:
result.append(u*v)
dp[i][j] = result
return dp[i][j]
#end def value
allvalue = value(0,n)
return allvalue
```
**本單元結束**
Sign in with Wallet
Connect another wallet