# Python-LeetCode 581 第14招 Dynamic Programming I： 基本原理與一維DP
「每一個DP背後都有一個dag，DP需要dag指引方向，如同視障者需要dog。」(Dynamic programming, Bottom-up)
「設計DP以尋找遞迴式開始，以避免遞迴來完成，除非，除非你準備小抄。」(Dynamic programming, Top-down memoization)
---
本單元介紹動態規劃(Dynamic Programming, DP)。DP名字中 Programming 是早年「規劃」的意思，指「以表格紀錄」，而非現在常用的「寫程式」，所以DP的意思是以變動的表格來求解的方法。
DP的應用很廣，變化很多，可以說是演算法解題的寶庫，在LeetCode與程式競賽中也用的非常多，程式競賽中甚至有許多困難而精妙的(優化)方法。LeetCode中的題目雖然不至於像競賽程式中的那麼難，但是因為變化較多且需要一些思考來解題，所以一般做LeetCode的人往往覺得DP是比較難的題型。LeetCode中的DP題目非常多，本教材不可能逐題講解，我們將對一些典型的題型分類講述，將分成三個單元。
## 基本原理
DP與分治有個相同之處，都是將問題劃分成**子問題**，再由子問題的解合併成最後的解，其中子問題是指**相同問題而比較少(小)的輸入資料**。所以，設計DP的方法從找出遞迴式開始，設計DP的演算法通常包含下面幾個步驟：
* 定義子問題。
* 找出問題與子問題之間的(遞迴)關係。
* 找出子問題的計算順序來避免以遞迴的方式進行計算。
如果沒有進行第三個步驟，而只是以遞迴的方式寫程式，就會變成純遞迴方式，純遞迴往往會遭遇效率不佳的問題，所以也可以說DP就是要改善純遞迴的效率問題的技術。我們先介紹兩個簡單的問題，以問題來舉例說明會比較清楚。
[(題目連結) 70. Climbing Stairs (Easy)](https://leetcode.com/problems/climbing-stairs/)
問題是說要上樓梯，每步走一階或兩階，如果走到第$n$階有$f(n)$種走法，輸入$n$，計算$f(n)$。例如$n=3$時，走法有1+1+1=3或1+2=3或2+1=3，一共3種，$f(n)=3$。
我們的問題是計算$f(n)$。
定義子問題：對$i<n$，$f(i)$表示走到第$i$階的走法數。接著要找出$f(n)$與子問題的遞迴關係，我們雖然沒辦法立刻寫出$f(n)$是多少，但是我們只要去想，走到第$n$階的最後一步一定是走了一階或兩階(沒有其他的可能)，而最後一步是一階與兩階的走法必然不同(沒有重複多算)。最後走一階的走法數就是抵達第$n-1$的走法數$f(n-1)$，而最後一步走兩階的走法數就是抵達第$n-2$階的走法數$f(n-2)$，因此，我們得到遞迴關係式$f(n)=f(n-1)+f(n-2)$，但是不要忘了以上推論是對於$n>2$時的狀況，遞迴的初始條件$f(1)$與$f(2)$要另外找，不難想一下就可以知道，所以完整的遞迴關係是：
$$
f(n) = \left\{
\begin{array}{ll}
n & \text{if } n<3 \\
f(n-1)+f(n-2) & \text{otherwise}
\end{array}
\right.
$$
如果直接依照遞迴寫程式，以下是這樣簡單的程式。
```python=
class Solution:
def climbStairs(self, n: int) -> int:
def f(n):
if n<3: return n
return f(n-1)+f(n-2)
#
return f(n)
```
這個程式可以跑，只要你不要輸入太大的數字。本題$n\leq 45$，上傳此程式會TLE，原因何在？這是一個純遞迴的程式，一個遞迴呼叫兩個，兩個就會呼叫四個，雖然$f(n-1)$與$f(n-2)$的呼叫次數並不一樣，但它會接近$2^n$，確切的時間複雜度大概是$O(1.618^n)$。
我們來把它改成DP，所以要進行第三步驟：找出子問題的計算順序來避免以遞迴的方式進行計算。什麼樣的計算順序會讓我們可以不需要遞迴呢？原則上「只要讓遞迴式等號右邊出現的在左邊的之前先算，並且用表格把算過的記下來，就可以不需要遞迴了。」以這一題為例，遞迴式$f(n)=f(n-1)+f(n-2)$，如果$n$從小往大算，算到$f(n)$的時候，$f(n-1)$與$f(n-2)$都已經算過了，所以只要當初算完的時候有記下來，那就可以直接從表格中取出$f(n-1)$與$f(n-2)$來相加得到$f(n)$，完全不需要用到遞迴。那麼如何用表格紀錄呢？這一題我們可以開一個陣列$F[]$，以$F[i]$記錄$f(i)$的值，程式就變成一個簡單的迴圈，沿著我們的計算順序($n$從小到大)，逐步從表格中取出值，計算後存入表格，程式如下：
```python=
class Solution:
def climbStairs(self, n: int) -> int:
F = [0,1,2]+[0]*43
for i in range(3,n+1):
F[i] = F[i-1]+F[i-2]
#
return F[n]
```
因為計算$f(i)$時只用得到前兩個值$f(i-1)$與$f(i-2)$，因此序列只需要保留最後兩個，更前面的算完就沒用了，所以我們可以節省陣列的空間，維護好序列的最後兩個就可以了，以下是更改後的程式。
```python=
class Solution:
def climbStairs(self, n: int) -> int:
if n<3: return n
a,b = 1,2 # f1, f2
for i in range(3,n+1):
a,b = b,a+b
return b
```
這個程式跑得很快，不過數字會成長的很快就是了，一般在考這一類題目的時候都要求輸出模某數的餘數。本題基本上就是非常有名的費式數列。我們還會再看到它。
我們完成了一個DP算法的設計，看起來並不是太難。請再回想一下剛才走過的思維步驟：定義子問題、找遞迴關係、最後找計算順序與定義表格來避免遞迴。所以DP從遞迴開始，但以去除遞迴來完成，看來似乎有點難，但以這題來說又很簡單。其實，對於大部分的題目，尋找計算順序與表格都很簡單，最常出現的計算順序就是像這一題：由小到大，而表格就是用遞迴的參數來直接定義。真正難的是遞迴關係式的尋找。
我們再來看一個例子。
[(題目連結) 64. Minimum Path Sum (Medium)](https://leetcode.com/problems/minimum-path-sum/)
問題是說有一個$m\times n$的方格圖，每個格子裡有一個非負整數。從左上角的格子出發，要到達右下角的格子，每一步只能向右或向下移動一格，找出一條路徑其所經過格子的數字總和最小。例如下圖中最小的路徑總和是深色部分的7。
我們把格子裡的數字當作走該格子的的成本，我們要找一條最小成本的路。每一步只能往右或往下，所以方格點可以看成一個DAG，這題就是個DAG上的最小權重路徑問題，它是個基本的DP問題。定義子問題：以$g(i,j)$表示出發點走到$(i,j)$的最小成本，以矩陣列與行的方式定義位置，出發點為$(0,0)$，終點是$(m-1,n-1)$。
接著要找出$g(i,j)$與子問題的遞迴關係，同樣的，我們不必立刻寫出$g(i,j)$是多少，只要去想，最後一步一定向右或向下，也就是前一個位置一定是$(i,j-1)$或$(i-1,j)$，根據定義，我們可以得到
$$
g(i,j)=\min\{g(i,j-1),g(i-1,j)\}+grid[i][j] \text{ for } i>0 \text{ and } j>0；
$$
初始條件為
$$
g(0,j) = \sum_{k\leq j}grid[0][k] \text{ for } j\geq 0 \\
g(i,0) = \sum_{k\leq i}grid[k][0] \text{ for } i\geq 0
$$
因為第0列的任何一個格子都只有一條可能的路徑，就是一直往右，第0行的狀況也是類似。得到遞迴式之後直接寫遞迴程式就是純遞迴，程式如下，再一次，遞迴的程式非常沒有效率：
```python=
class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
m,n = len(grid), len(grid[0])
def g(i,j):
if i==0:
return sum(grid[0][:j+1])
if j==0:
return sum(grid[k][0] for k in range(i+1))
return min(g(i-1,j), g(i,j-1))+grid[i][j]
return g(m-1,n-1)
```
要把純遞迴改成DP，就要找計算順序，讓遞迴關係式右邊的出現在左邊的之前，本題的遞迴式為：$g(i,j)=\min\{g(i,j-1),g(i-1,j)\}+grid[i][j]$，簡單觀察可以得知，只要$i$與$j$都從小到大就可以滿足需要，所以我們可以採取「由上而下，由左而右」的順序，當然也可以「由左而右，由上而下」，甚至可以沿著$i+j$由小而大的斜線的順序，有點自找苦吃就是了。至於表格，最直覺的方式就是將$g(i,j)$記錄在一個二維陣列，本題可以直接存在原來輸入的grid中。
以下是程式，跑得很快，時間複雜度是$O(mn)$，而遞迴版本的複雜度則是組合數$comb(m+n-2, m-1)$。
```python=
class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
m,n = len(grid), len(grid[0])
for i in range(1,m):
grid[i][0] += grid[i-1][0]
for i in range(1,n):
grid[0][i] += grid[0][i-1]
for i in range(1,m):
for j in range(1,n):
grid[i][j] += min(grid[i-1][j], grid[i][j-1])
return grid[m-1][n-1]
```
### 狀態轉移
DP子問題的遞迴關係式也有人稱為「狀態轉移」，這個名詞大概是從有限狀態機(數位電路設計)來的。子問題可以看成一個狀態，目前的狀態是根據之前的那些狀態，這樣的轉換關係就稱作狀態轉移，設計DP時，最重要的就是找出狀態轉移。
之前我們將子問題看成「部分解」，所以是在找部分解與更小的解之間的關係，這兩個講法只是描述的方式不一樣，其實是同一回事，有的時候這樣想比較方便，有的時候那樣想比較直覺。
我們說狀態A是狀態B的前置狀態(predecessor)，如果狀態B是由A轉移過來的，一個狀態可能有多個前置狀態，通常一個狀態的值是由它的前置狀態的值做某些計算得到。如果我們把每個狀態想像每一個點，若A是B的前置狀態，則由A畫一個箭頭指到B，我們會得到一個圖(graph)，這個圖就是這個DP的狀態轉換圖，在圖論上來說，它必然是個有方向但沒有環路的圖(directed acyclic graph, dag)。遞迴關係不會無限遞迴，所以必然沒有環路。我們來看看前面兩個簡單的問題的狀態轉移。
上樓梯問題的子問題是走到第$i$階，關係式$f(n)=f(n-1)+f(n-2)$，所以狀態圖如下，也就是每個狀態由它的前兩個狀態轉移而來。
第二個問題是方格圖的問題，遞迴式是$g(i,j)=\min\{g(i,j-1),g(i-1,j)\}+grid[i][j]$，其中$grid[i][j]$是輸入的資料，每一個格子是一個點(狀態)，前置狀態是他的左方與上方的格子。它的狀態轉換圖類似下圖：
對於一個dag，我們一定可以將它的所有點排成某個順序，在此順序中，每個箭頭都由前往後指，也就是說，每個點的前置點都在它之前，這樣的順序稱為拓樸順序(topological sort)，我們的DP就是要沿著一個拓樸順序來進行。有件事情要提醒，本節說明的狀態轉移以及dag與拓樸順序，是方便思考用的，在DP解題時，將圖建出來可能會太花時間，通常並不需要把它建出來，也就是建在心中就可以了，不必建在程式中。
### 分類與複雜度
題目的分類往往有很多種，主要看目的何在而分類，這裡我們以便於理解與學習來分類。網路上有一些教學文件將DP分成非常多類，各家的分類方法並不一致，有些問題也可能歸屬不同類型。
本系列的筆記簡單將DP分成：
* 一維DP
* 二維DP
* Tree DP
* Set DP (Bitmask DP)
主要是根據遞迴式的類型來做區分。另外因為本系列筆記編排的原因，有些DP問題並為收納在DP的單元，而是出現在其他單元，例如Graph上的DP。
DP演算法的時間複雜度通常都比較好計算，若有$O(P)$個狀態，每個狀態有$O(Q)$個前置狀態，則時間複雜度就是$O(PQ)$。
在演算法發展歷史上，有為了DP優化而將DP做以下分類：一個DP如果狀態有$O(n^x)$而轉移式涉及$O(n^y)$個狀態，則稱為$x$D$y$D的DP，例如小朋友上樓梯是1D0D的，因為有$n$個要算，每次算$f(i)$只涉及2個$f(i-1)$與$f(i-2)$。方格路徑的問題則是2D0D，因為有$n^2$(假設$m=n$)個要算，每次只需要2個(左方與上方)。當然也有一些DP不在這個分類中。
一個xDyD的DP，如果沒有優化，很明顯的，時間複雜度就是$O(n^{x+y})$，一般來說若$y=0$時比較簡單，因為遞迴式單純，而且遞迴式找出來時，程式就已經差不多寫完了，因為套個迴圈依序計算就是了。$y=1$的DP題目通常遞迴式較複雜不容易想到，所以比較難，而且可能存在某種優化或需要某些資料結構幫忙來降低複雜度，所以會比較難。不過LeetCode的DP只會涉及簡單的優化，而不像競程那樣可能有很多種精妙的優化招數。
### Top-down memoization
前面講到設計DP算法的步驟，基本上要先找出遞迴式，然後找出計算順序來避免遞迴。這算是標準的DP，也稱為Bottom-up的DP。另外有一種實現DP的方式是不找計算順序，直接依照遞迴式寫遞迴，但是因為一定要避免遞迴的重複計算，所以採取了一些步驟，這種實現的方式稱為top-down memoization的DP，其中**memoization**在字典上應該沒有這個字，大概是為了這個技術自己創造的，這個字是由memo(備忘錄，便籤小紙條)變來的，這個方法基本上應該是打比賽或重實作的人上發展出來的(偷懶)方法，因為從理論的角度，除了程式比較好寫之外，這麼做沒有好處，但考試與比賽還真的就希望比較好寫。
用比較俏皮的講法，這個方法就是再找到遞迴式之後，直接寫成遞迴版本的程式，但要加上三個動作：
1. 開一個表格當作小抄，用來記錄計算過的結果，表格初值設為某個不可能的值，用以辨識是否曾經算過。
2. 在遞迴之前，先偷看一下小抄是否曾經算過，如果小抄上有答案(已經算過)，則直接回傳答案。
3. 如果小抄上沒有，就遞迴呼叫，但計算完畢回傳前，要把它記在小抄上。
我們來看看前面介紹的兩個問題的遞迴版本如何改成top-down DP。下面是第一題，
```python=
class Solution:
def climbStairs(self, n: int) -> int:
F = [0]*(n+1) # memo
def f(n):
if n<3: return n
if F[n]>0: return F[n]
F[n] = f(n-1)+f(n-2)
return F[n]
#
return f(n)
```
首先注意到它就是拿前面的遞迴版本來改的，修改的部分：第3行初始了一個列表$F[]$，都是0；在遞迴函數中第6行做了一個檢查是否$F[n]>0$的動作，如果是，則直接回傳，這一題的數字都是正數，所以我們可以用0來表示沒算過；如果沒算過，第7行就真的遞迴呼叫去計算，然後存在表格中再回傳。
這個**遞迴**的程式跑得慢不慢呢？基本上跟迴圈版的DP跑得一樣神速。
我們再來看第二題方格路徑的改法。下面是修改版的程式，其實每一個top-down的DP幾乎都是長的這個樣子。
```python=
class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
m,n = len(grid), len(grid[0])
G = [[-1]*n for i in range(m)]
def g(i,j):
if i==0:
return sum(grid[0][:j+1])
if j==0:
return sum(grid[k][0] for k in range(i+1))
if G[i][j]>=0: return G[i][j]
G[i][j] = min(g(i-1,j), g(i,j-1))+grid[i][j]
return G[i][j]
return g(m-1,n-1)
```
第4行初始了一個二維陣列$G$，初值$-1$來表示沒有計算過，這題的輸入值均為非負。遞迴函數中第10行加了一個如果算過就直接回傳。否則呼叫遞迴並將結果存入表格中後回傳。這個程式也是跑得跟DP版一樣的神速。
### Python memoization
Python在functools中提供了一個函數的decorator來自動做memoization，只要在函數前加上
@lru_cache(maxsize=None)
就會對此函數做memoization，也就是說，函數計算過的結果會被記錄下來，如果再用相同參數呼叫過此函數，它就會將之前的結果直接回傳而不進行計算。這與我們手動做的memoization是一樣的。於是前面的top-down memoization DP可以變得更簡化。
例如，之前的上樓梯的題目，只要在遞迴版的副程式定義前加上一行就好了。
```python=
class Solution:
def climbStairs(self, n: int) -> int:
@lru_cache(maxsize=None)
def f(n):
if n<3: return n
return f(n-1)+f(n-2)
#
return f(n)
```
第二個找最小成本路徑的例子也是一樣。
```python=
class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
m,n = len(grid), len(grid[0])
@lru_cache(maxsize=None)
def g(i,j):
if i==0:
return sum(grid[0][:j+1])
if j==0:
return sum(grid[k][0] for k in range(i+1))
return min(g(i-1,j), g(i,j-1))+grid[i][j]
return g(m-1,n-1)
```
Top-down的DP基本上是個偷懶的方法，我們的建議如下：如果計算順序不難找，還是寫迴圈版，不要過分偷懶，因為遞迴還是有成本與限制，尤其某些系統之下(尤其架在視窗系統下)，遞迴的深度有一定的限制，超過限制會導致執行階段的錯誤。
在計算順序比較不好找或者比較麻煩時，而且系統是允許的狀況下，採用top-down遞迴的寫法程式碼會比較減短。最常見的情形就是Tree的DP，遞迴的DFS版本要比迴圈版的bottom-up順序簡潔。不過這裡還是要建議：兩種都要會，可以偷懶的時候才偷懶。
至於自己寫memoization或是使用lru_cache則沒有特別的建議，最好也是兩者都要會。
## 一維DP例題
一維的DP基本上輸入資料是個序列，但也有可能是經轉換後變成序列的。DP的問題往往讓人覺得精妙，也就是不會的時候覺得很難，一旦弄懂了就覺得很簡單。下面第一題就是個經典的精妙DP。
[(題目連結) 53. Maximum Subarray (Medium)](https://leetcode.com/problems/maximum-subarray/)
給一個整數陣列$nums$，要找最大總和的子陣列。子陣列就是連續的一段，本題定義為非空子陣列。非空與沒有非空的要求只差別在：當全部都是負值時，答案會不同。
陣列中可能有負值，否則整個陣列的總和就是答案。以DP的思考方式，先定義子問題，以最直接的方式定義子問題：令$d[i]$是以位置$i$結尾的最大總和，最後的答案就是 max($d$)，也就是各種可能的結尾中挑最大。第二步找遞迴式，我們要思考的是$d[i]$與$d[i-1],d[i-2],\ldots$有何關係。
以$i$結尾的最大總和，可以分為：包含$i-1$與不含$i-1$兩種：
1. 若不含$i-1$，那就是只有$nums[i]$；
2. 若包含$i-1$，就是$nums[i]$加上$i-1$結尾的最大總和，根據定義，$i-1$結尾的最大總和就是$d[i-1]$。
兩者取較大的就是$d[i]$，也就是
$$
d[i]=\max\{nums[i], d[i-1]+nums[i]\}
$$
也可以寫做$d[i]=\max\{0, d[i-1]\}+nums[i]$。初始條件為$d[0]=nums[0]$。
第三步計算順序，很顯然$i$從小算到大就是個不須遞迴的DP順序。
DP的題目大多是方法較難，程式好寫。根據找到的關係式直接定義變數，照寫就可以。這一題當然可以開一個list $d$，這是個1D0D的DP，因為每一個$d[i]$只需要用到前一項，我們可以節省空間不需要開一個list。另外一個節省空間的寫法就是本題可以把$d$直接存在輸入list的$nums$中。
以下是範例程式，我們從$i=1$開始，連初始條件都不需要寫了。時間複雜度$O(n)$。
```python=
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
for i in range(1,len(nums)):
if nums[i-1]>0:
nums[i] += nums[i-1]
return max(nums)
```
接下來三題是一個系列，故事是說你是個專業的盜匪，在一晚上要選擇一群房子中的某些進行偷盜，條件是不可以偷兩間相鄰的房子，否則會驚動警察。給定偷盜每間房子的利益，請問如何選擇可以獲得最大利益總和。
在圖論中，一群不相鄰點稱為independent set。所以強盜系列的題目是在找max independent set，但一般圖的independent set是NP-hard的問題，此三題都是在非常簡單的圖形類型下的問題。
[(題目連結) 198. House Robber (Medium)](https://leetcode.com/problems/house-robber/)
第一個上場的問題是房子排成一列，簡單說，本題是給一個非負整數陣列$nums$，求一群不相鄰的格子的最大總和。
DP的問題，最重要的就是遞迴式，而遞迴式取決於定義子問題(狀態)，定義不同列出的遞迴式也就不同，有的簡單，有的比較複雜。我們以這一個簡單的題目來說明一下思考的方式。
這一題是序列，很自然將前$i$個的解定義成子問題。若定義$d[i]$是前$i$個的最大子陣列總和，也就是輸入為$nums[:i+1]$時的最佳解。那麼，與$d[i-1]$的關係是什麼呢?這裡我們遇到一點困難，因為選了$i$當然不能選$i-1$，我們不知道$d[i-1]$有沒有選$i-1$，所以$d[i]$與$d[i-1]$並無明顯的關係。
DP在找子問題的關係，找不到的時候有一個方法就是在將子問題進一步分類，也就是引入另外一個參數。我們將$i$之前的解進一步區分成：
$d0[i]$是$i$之前的最大解但沒有選$i$；
$d1[i]$是$i$之前的最大解且選了$i$。
這樣我們很容易可以得到
$d0[i]=\max(d0[i-1],d1[i-1])$
$d1[i]=nums[i]+d0[i-1]$
初始條件是$d0[0]=0, d1[0]=nums[0]$，最後的答案是$\max(d0[n-1],d1[n-1])$。
這樣可以做了，時間複雜度是$O(n)$。
我們也可能換一個想法。定義$d[i]$是最後選$i$的最大總和，但$d[i]$與$d[i-1]$並無明顯的關係，那麼$i$之前被選取的會是哪一格呢？也就是從狀態轉移的觀點，$i$的前置狀態會是哪些？
直覺的想可能$i-1$之前的任一點都可能是前一點，那麼就會導致
$$
d[i] = \max_{j<i-1}\{d[j]\}+nums[i]
$$
如果直接依照這個關係式去做，會導致一個$O(n^2)$的解，因為有$O(n)$個$d[i]$，每一個要花$O(n)$的時間找一個max。
但仔細看這個max，其實是個prefix_max(d[i-2])，令$p[i]=\max_{j\leq i}d[j]$是$d[i]$的前綴最大，我們可以得到
$$
\begin{array}{l}
d[i] = p[i-2]+nums[i] \\
p[i] = max\{p[i-1],d[i]\}
\end{array}
$$
初始條件$p[0]=d[0]=nums[0]$、$d[1]=nums[1]$以及$p[1]=\max\{nums[0],nums[1]\}$。最後的答案在$p[n-1]$。這樣又得到了一個$O(n)$時間複雜度的解法。
回到定義$d[i]$是最後選$i$的最大總和的情況下，如何找前置狀態的問題。因為本題的數字都是非負整數，所以一定有一個最佳解滿足：**不會連續三個都不選**。
因為連續三個都不選的話，我們可以把三個的中間挑起來，不會與其他選取的相鄰。所以，前一個挑選的不可以是$i-1$，而一定是$i-2$或$i-3$，那麼立刻得到一個遞迴式
$$
d[i] = \max\{d[i-2],d[i-3]\}+nums[i]
$$
初始條件是$d[0]=nums[0]$、$d[1]=nums[1]$以及$d[2]=nums[2]+nums[0]$，最後的答案在$\max\{d[n-2],d[n-1]\}$。這樣也是一個時間複雜度$O(n)$的解。
回到原始的問題定義。前面是把$d[i]$的定義成最後一個選在$i$，如果我們一開始就有前綴最佳的想法，也就是$d[i]$的定義改成**在$i$之前(含)的最佳解，但不一定有選$i$點**，那麼$d[i]$有兩種情形：選了$i$或是沒選$i$。如果選了$i$，那麼$i-1$不能選，前面最好的解就是$d[i-2]$，所以$d[i]=nums[i]+d[i-2]$；否則，沒有選$i$，那最佳解就是$d[i-1]$。我們就得到以下遞迴式
$$
d[i]=\max\{d[i-1], d[i-2]+nums[i]\}
$$
初始條件$d[0]=nums[0]$與$d[1]=\max\{nums[0],nums[1]\}$，最後的答案在$d[n-1]$。這也是個$O(n)$時間複雜度的解，而且遞迴式最簡潔。
這是一個簡單的題目，我們舉出了四種可能的遞迴關係式的思考方式，很多DP的問題都像這樣可能會有不同的思路最後找出不同的解法，這些解法骨子裡其是是等價的。當然如果多看多做題目，對於思考會有幫助，但即使是陌生的題目，依循著DP的思維，通常可以找到可行的解，當然非常難的題目是另當別論，至少在LeetCode中的題目大多數都不至於太難。
以下是實現最後一個遞迴式的範例程式。因為只需要用到前兩項，我們節省記憶體就不開列表，只用兩個變數prev與curr代表$d[i-2]$與$d[i-1]$，每次計算出$d[i]$放在$t$中，然後更新前兩項即可。時間複雜度$O(n)$。
```python=
class Solution:
#dp[i] = max(dp[i-1], dp[i-2]+p[i])
def rob(self, nums: List[int]) -> int:
if len(nums)==1: return nums[0]
prev = nums[0] #dp[i-2]
curr = max(nums[0], nums[1]) #dp[i-1]
for x in nums[2:]:
t = max(curr, x+prev)
prev, curr = curr, t
return curr
```
接著是強盜系列的第二題。
[(題目連結) 213. House Robber II (Medium)](https://leetcode.com/problems/house-robber-ii/)
題目十分類似，只是原來房子排成一列改成排成一個頭尾相接的環路，也就是第0間與第$n-1$間是相鄰的，不可以同時選取。
頭尾相鄰的問題通常跟一列的問題只差一點點，只要將環路從某點切開後就變成一列的問題了。以本題來說，我們可以區分成第0間有沒有選：如果選了第0間，最後一間不能選，cycle就斷開變成序列了；如果沒選第0間，就是在$nums[1:]$序列中求解。
以下是範例程式。這次我們不省記憶體以開列表的方式示範。第8 ~ 11行是一定不選0的狀況，遞迴式跟前題一樣，只是初始狀況有點小差異，得到的解存在ans1。
第13 ~ 16行是一定選了0的狀況，所以初始條件$dp[0]=dp[1]=nums[0]$。最後兩個答案挑最大的就是答案，時間複雜度$O(n)$。
```python=
class Solution:
def rob(self, nums: List[int]) -> int:
n = len(nums)
if n==1: return nums[0]
if n==2: return max(nums)
dp = [0]*n
# without 0
dp[1] = nums[1]
for i in range(2,n):
dp[i] = max(dp[i-1], dp[i-2]+nums[i])
ans1 = dp[n-1]
# with 0
dp[0] = nums[0]
dp[1] = nums[0]
for i in range(2,n-1):
dp[i] = max(dp[i-1], dp[i-2]+nums[i])
return max(dp[n-2],ans1)
```
偷盜系列的第三題。
[(題目連結) 337. House Robber III (Medium)](https://leetcode.com/problems/house-robber-iii/)
題目改成房子的排列是一個binary tree，一樣相鄰的不可以選，要找滿足條件的點權值最大總和。這題是tree max weight independent set，因為在圖論中不相鄰的點集合稱為獨立集。題目給的不是任意樹狀圖，而是LeetCode給定的二元樹結構。
Tree的independent set如果沒有加權(點數最大)，可以用貪心法則求，如果有加權(本題)是樹狀圖的DP。對於樹狀圖的DP，最常見的子問題定義方式就是以某個$v$點為root的subtree，本題也不例外，我們定義$d1[v]$與$d0[v]$分別是選取與不選取根節點$v$的條件下，該subtree的最佳解。若$v$點有選，他的孩子都不能選，因此
$d1[v] = v.val + d0[v.left]+d0[v.right]$
反之，若$v$沒有選，他的孩子都可選可不選(挑較大者)，因此
$d0[v] = \max(d1[v.left],d0[v.left])+\max(d1[v.right],d0[v.right])$
根據這兩個遞迴式可以來實作程式，樹狀圖的DP可以top-down也可以bottom-up，但本題是指定的binary tree的結構，所以就遞迴下去，每次回傳兩個值$(d1,d0)$。
以下是範例程式。第11行是初始狀態的空節點，理論上應該回傳(-oo,0)，但此處放(0,0)沒差別。其他就依照遞迴式寫就可以了。最後的答案有取與不取root中挑比較大的。時間複雜度$O(n)$。
這題當然也有其他的寫法。此外，Tree DP我們將在下一單元看到其他的例子，這題因為同一系列就放在這裡了。
**註：** 常常講到這題的時候都會勾起筆者的回憶。印象深刻且覺得有趣的事情是，1989年筆者考台大資工研究所碩士班的考題中就碰到這題:max weight independent set on a tree。當然那個年代是筆試，只要推出遞迴式與寫出虛擬碼就行了。而且包含筆者在內的大多數考生都沒有修過演算法，所以這在當時其實應該算是非常難的題目。至少筆者在進入考場前是完全沒見過這個題目。但憑藉著一些知識與思考，筆者在考場做出了這題，就憑這題大概就錄取了，那個時候台大很喜歡一科只考五題，一題20分，不會寫而得0分的大有人在。筆者當年的演算法功力當然比現在差很多，有趣的是，整體學生的演算法能力進步得非常多，包含程式比賽也是這樣，當年會個簡單DP就很厲害可以打天下了，而現在會DP只是基本條件。
```python=
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
# return (max with root, max without root)
def rob(self, root: Optional[TreeNode]) -> int:
def dp(r):
if not r: return (0,0)
le1,le0 = dp(r.left)
ri1,ri0 = dp(r.right)
return (r.val+le0+ri0, max(le1,le0)+max(ri1,ri0))
#
return max(dp(root))
```
接下來4題是同一個系列的，難度由易到難。問題是說給你某商品(股票)每日的價格，要找到最大的可能獲利。4題的條件略有不同。
[(題目連結) 121. Best Time to Buy and Sell Stock (Easy)](https://leetcode.com/problems/best-time-to-buy-and-sell-stock/)
第一題很簡單，條件是：先買後賣，只能買賣一次，如果無法獲利，答案給0。
考慮每一天當賣點的最大獲利，再從其中取最大值就是答案。第$i$天賣出的最大獲利當然就是在$i$之前的最小值買入，所以這一題的答案其實就是
```python
max(max(prices[i] - min(prices[:i]) \
for i in range(1,len(prices))),0)
```
當然不能這麼寫，因為時間複雜度會跑到$O(n^2)$。在$i$之前的最小值也就是prefix minimum，與前綴和一樣，很簡單的DP就可以線性時間算出所有prefix minimum，因為若$pmin[i]$表示前$i$項的最小值，則$pmin[i] = \min(pmin[i-1],prices[i])$。
跟前一題一樣，計算時只需要前一項的結果以及前一項的前綴最小，我們可以用$O(1)$ space而不需要開list。以下是範例程式。初始時$pmin$給個不可能的大，最佳獲利$prof$給0。跑一個迴圈依序歷遍所有價格$p$，先計算$p$賣出的最大獲利，並與最佳解取max，然後更新$pmin$。時間複雜度$O(n)$。
```python=
class Solution:
def maxProfit(self, prices: List[int]) -> int:
pmin = 10000
prof = 0
for p in prices:
prof = max(prof, p-pmin)
pmin = min(pmin, p)
return prof
```
[(題目連結) 122. Best Time to Buy and Sell Stock II (Medium)](https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/)
跟前一題一樣是股票最大獲利，條件改成可以買賣無限多次，但任何時候最多只能持有一股。
其實就是所有上升波段的總和，因為沒有買賣成本，也可以想成每一天價格如果比前一天高，就把$prices[i]-prices[i-1]$納入獲利。如果價格下降，就不理。
所以這一題可以一行就搞定。以下是範例程式。我們用zip(prices[1:],prices)產生所有(prices[i],prices[i-1])的tuple，相減後與0取max再做加總，就是答案。
時間複雜度$O(n)$。
```python=
class Solution:
def maxProfit(self, prices: List[int]) -> int:
return sum([max(x-y,0) for x,y in zip(prices[1:],prices)])
```
[(題目連結) 123. Best Time to Buy and Sell Stock III (Hard)](https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/)
與前兩題一樣要找最大獲利。條件改成：**先買後賣，最多只能做兩次交易，第一次賣了之後才能再買**。
根據前一題的說明，我們知道如何計算第一次賣在$i$的最大獲利，我們對第一次的獲利做一次前綴最大的計算可以得到第一次賣在$i$之前的最大獲利，令這個值是$p[i]$。第二次賣在$i$的最大獲利則是買在某個$j<i$的獲利加上$j$以前的一次買賣獲利，也就是
$$
\begin{array}{ll}
& \max_{j<i}\{prices[i]-prices[j]+p[j-1]\} \\
=& prices[i]+\max_{j<i}\{p[j-1]-prices[j]\}
\end{array}
$$
因為在第$j$日賣出再以同樣價格買入並不會增加獲利，所以後半部也可以寫成$\max_{j<i}\{p[j]-prices[j]\}$，也就是說，我們一路掃過去，只要維護好$p[j]-prices[j]$的prefix maximum就行了。
以下是範例程式。第5 ~ 9行跟前一題一樣是計算一次買賣的獲利，但我們存在$p[]$且取前綴最大(第8行)，接著再掃一次，根據上面的式子維護前綴最大與計算獲利。時間複雜度$O(n)$。
這兩個迴圈是可以合併成一個迴圈，但分步驟寫也許比較清楚一點。
```python=
class Solution:
def maxProfit(self, prices: List[int]) -> int:
# the first profit
n = len(prices)
p = [0]*n # prefix max profit
pmin = prices[0]
for i in range(1,n):
p[i] = max(p[i-1], prices[i]-pmin)
pmin = min(pmin, prices[i])
# total profit(sell at i) = prices[i] - prices[j] + profit_before_j
pp = [0]*n
pmax = p[0] - prices[0]
prof = 0
for i in range(1,n):
prof = max(prof, prices[i]+pmax)
pmax = max(pmax, p[i]-prices[i])
return prof
```
[(題目連結) 188. Best Time to Buy and Sell Stock IV (Hard)](https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/)
與前兩題一樣要找最大獲利。條件改成：**先買後賣，最多只能做$k$次交易，第一次賣了之後才能再買**，其中$k\leq 100$是輸入參數，而序列長度$n\leq 1000$。
本題是前一題的延伸，將2次增加為$k$次，基本上只要照相同的方法做$k$次就可以了，但是因為$k$是個變數，我們要把它改成迴圈的形式。
令$d[k][i]$是在$\leq i$做了$k$次買賣的最大獲利，以下兩種情況取最大：最後一次如果是賣在$i$之前，$d[k][i]=d[k][i-1]$；否則，最後賣在$i$的情況時，
$$
\begin{array}{lll}
d[k][i]&=& \max_{j<i}\{prices[i]-prices[j]+d[k-1][j]\} \\
&=& prices[i]+\max_{j<i}\{d[k-1][j]-prices[j]\}
\end{array}
$$
這個計算式變成了二維，原則上應該用一個二維陣列來做，但是因為每一列只需要前一列的資料，所以我們可以用兩個一維陣列來做，每次從$d[]$算到$t[]$，迴圈結尾再將$d,t$交換，用交換比用copy來得好，因為交換list物件只需要$O(1)$但是copy需要$O(n)$。此外，看起來第一次要單獨做，但是我們可以虛擬的設第0次的獲利是0，就可以放在迴圈內一起處理。
以下是範例程式，時間複雜度$O(kn)$，請注意我們每次都由$d$算到$t$。交替用兩個一維陣列來做的方法有時稱為**滾動陣列**。
```python=
class Solution:
def maxProfit(self, k: int, prices: List[int]) -> int:
n = len(prices)
d = [0]*n # profit <= i
t = [0]*n
# compute from d to t
for it in range(k):
t[0] = 0
pmax = d[0] - prices[0] # best profit - buy_price
for i in range(1,n):
t[i] = max(t[i-1],prices[i]+pmax) # sell at i
pmax = max(pmax, d[i]-prices[i])
t,d = d,t
return d[n-1]
```
**補充說明：** 本題有一個更難的版本，當$k$很大的時候，上述方法的複雜度來到$O(n^2)$。這題有個解法可以做到$O(n\log n)$，但超過了LeetCode應該有的難度，筆者曾經在全國高中程式賽中出過這樣的題目。
[(題目連結) 446. Arithmetic Slices II - Subsequence (Hard)](https://leetcode.com/problems/arithmetic-slices-ii-subsequence/)
給一個整數序列，找出有多少個子序列是等差數列，等差數列的定義是長度3以上(含)，任相鄰兩項的差皆是相同的。輸入序列長度$\leq 1000$，數字範圍為32位元整數。
很自然的想法，我們對於每一個index $i$，算出$nums[i]$結尾的等差數列。一個等差數列需要兩個參數來決定，除了$i$結尾之外，我們再把公差$dif$納入。令$dp[i][dif]$是以$i$結尾而公差為$dif$的等差數列個數。當掃描到$i$的時候，對每一個$j<i$來檢查$dp[j][dif]$，其中$dif=nums[i]-nums[j]$，顯然，造成$dp[j][dif]$的每一個子序列都可以再加上$i$，因此，$dp[i][dif] = \sum_{j<i}(dp[j][dif] + 1)$，其中的加一是納入$(j,i)$這個子序列。這樣計算有兩點要留意：
1. 可能的公差$dif$不是小範圍的整數，所以我們要用字典來處理。
2. 我們沒有排除長度為2的子序列，最後要把它扣除。
以下是範例程式。我們的字典用Counter()來簡化，不存在時預設值0。第7行的$dp$是$n$個Counter()的list，第$i$個對應$i$結尾。跑一個雙迴圈，對每一個$i$結尾，嘗試每一個$j<i$，
第11行把每一個$j$結尾公差為$dif$都納入為$i$結尾，在$j$迴圈結束後，將所有$i$結尾的數量利用dict.values()取出後加總並納入total。最後，我們扣除所有長度2的子序列(第14行)。
時間複雜度$O(n^2)$。
```python=
class Solution:
# dp[i][d] = length of seq end at i and diff=d
# O(n^2)
def numberOfArithmeticSlices(self, nums: List[int]) -> int:
n = len(nums)
total = 0
dp = [Counter() for i in range(n)]# dict with default 0
for i in range(n):
for j in range(i):
dif = nums[i]-nums[j]
dp[i][dif] += dp[j][dif] + 1
total += sum(dp[i].values())
# end for
total -= n*(n-1)//2
return total
```
**Longest Increasing Subsequence (LIS)**
一個序列的子序列是指可以任意挑選某些成員，但是不可以交換他們的前後順序，也可以說是刪除某些元素。
先看一個LeetCode上的LIS裸題。
[(題目連結) 300. Longest Increasing Subsequence (Medium)](https://leetcode.com/problems/longest-increasing-subsequence/)
給一個序列$nums$，LIS就是找出最長的遞增子序列。如果把序列中每個元素看成一個點，若且惟若$i<j$且$nums[i]<nums[j]$則存在一條有向邊$i\rightarrow j$。這樣造出來的會是一個DAG(不是DOG喔)，這個DAG上的任何一條路徑都是一個遞增子序列，所以LIS就是這個DAG上的最長路徑。
如果肯把這個DAG建造出來，求LIS並非難事，因為DAG上的最長路徑就是個沿著拓普順序的基本DP。
但是這樣做需要花$O(n^2)$的時間，因為可能的邊就有$O(n^2)$條。以下是這樣的程式，可以通過時間排名還不差，因為這一題的參數設定$n\leq 2500$是要讓$O(n^2)$可以通過的。請留意$(0,1,2,\ldots n-1)$就是一個topological sort，而且我們並不需要先建DAG再做，而是一路找後繼點來修改它的長度。
```python=
class Solution:
# O(n^2) build dag and find longest path
def lengthOfLIS(self, nums: List[int]) -> int:
n = len(nums)
d = [1]*n # longest path ended at i
for i in range(n):
for j in range(i+1,n):
if nums[i]<nums[j] and d[i]+1>d[j]:
d[j] = d[i]+1
return max(d)
```
令$d[i]$是最後一點在$i$的最長LIS長度，我們如果寫下遞迴式，將會是
$$
d[i] = \max\{d[j]: j<i \text{ and } nums[j]<nums[i]\} + 1
$$
初始條件是$d[i]=1$如果$i$沒有前置點，最後的答案是$\max_i d[i]$。這是個1D1D的DP，直接做就是$O(n^2)$。我們可以優化這個DP。
算法的效率來自1.避免重複的計算；2.避免不需要的計算。前述DP將同一個點結束的子序列歸成一類，已經避免了重複的計算。我們來考慮有那些沒有用的計算。
假設我們已經做到第$i$個點。對於$j<i$，若$nums[i]\leq nums[j]$而$d[i]\geq d[j]$，也就是$i$是比較小的結尾但是有比較長的LIS，那麼$j$顯然是沒有用的，因為可以接在$j$後面的一定也可以接在$i$後面，而接在$i$後面可以得比較好的結果。
如果我們刪除那些沒有用的子問題結果，會剩下甚麼呢？**每一種可能的長度只會有一個點被留下來**，LIS長度為$l$而被留下來的就是「長度$l$的最小可能結尾」。如果我們將這個資料存放在一個陣列$last[]$，這個陣列的元素是單調遞增的，在第$i$個回合計算$d[i]$時，我們搜尋找到
$l=\max\{j: last[j]<nums[i]\}$，
於是我們得到$d[i] =l+1$，最後我們要將$d[i]$的資料納入，也就是說$l+1$的長度多一個可能結尾是$nums[i]$，因此，我們需要更新 $last[l+1]=\min\{last[l+1],nums[i]\}$。
請稍等，還記得$l$是怎麼來的嗎？$l$是小於$nums[i]$的最大的那一個$last[]$，也就是說除非$l$是$last[]$的最後一個元素，否則$last[l+1]\geq nums[i]$，因此根本不必多做一次比較。
記得$last[]$是個單調遞增的陣列嗎？也就是長度越長的結尾越大，既然是單調陣列當然就可以二分搜了，二分搜可以用bisect.bisect_left()來找，LeetCode的環境已經import bisect了，可以直接呼叫。
以下是範例程式。初始時$last$放一個-oo的值當哨兵，任何輸入的數都至少可以接在它後面，也就不需要處理初始狀況。對輸入的每一個數字$s$，二分搜bisect_left回傳的是第一個$\geq s$的index，如果是$last$的結尾，就新增$s$，否則將$last[i]$改成$s$。程式簡潔而優雅。
時間複雜度$O(n\log L)$，其中$L\leq n$是LIS的長度，所以也可以說是$O(n\log n)$。
```python=
class Solution:
# last[i] is smallest last val of length i
# last will be strictly increasing
def lengthOfLIS(self, nums: List[int]) -> int:
last = [-10001] # sentinel
for s in nums:
i = bisect_left(last,s)
if i >=len(last):
last.append(s)
else:
last[i] = s
return len(last)-1
```
再看一個延伸題，它是要算LIS的數量。
[(題目連結) 673. Number of Longest Increasing Subsequence (Medium)](https://leetcode.com/problems/number-of-longest-increasing-subsequence/description/)
要計算LIS的數量，對於每一點，我們需要紀錄該點結束的LIS長度以及數量，以下是把DAG擺在心中的直接寫法。時間複雜度$O(n^2)$。
```python=
class Solution:
# direct method dp[i]=(longest length, num) ended at i
def findNumberOfLIS(self, nums: List[int]) -> int:
n = len(nums)
d,p = [1],[1] # length and num ended at i
for i in range(1,n):
longest,num = 0,1
for j in range(i):
if nums[j]>=nums[i]: continue
if d[j] > longest:
longest = d[j]
num = p[j]
elif d[j] == longest:
num += p[j]
# else:pass do nothing
d.append(longest+1)
p.append(num)
# find ans
longest = max(d)
num = sum(p[i] for i in range(n) if d[i]==longest)
return num
```
其實這題上述直接的寫法已經是很好的做法了，筆者繳交時時間排行已經是95%了。
延伸前面二分搜的方法，對於每一個長度$i$，我們不只存最小結尾$last[i]$，若每一點$j$結尾的最長LIS長度為$i$數量為$f$的話，我們在$D[i]$中紀錄一筆$(nums[j],f)$，意即結尾數值與個數。
當我們歷遍到序列某個數$x$時，我們先二分搜$last$找到$x$結尾最大長度是$i$，然後把$D[i-1]$中結尾比$x$小的數量都加起來，就是$x$結尾的數量了。
以下是範例程式。可以參照對比前一題只算LIS長度的範例程式。Worst case時間複雜度還是$O(n^2)$。原因在第9行這個sum可能會花到$O(n)$的時間。假設第9行這個動作可以在$O(T)$時間完成，那麼時間複雜度將是$O(n(\log n+T))$。在多數情形下，$T$並不大，但Worst case有可能是$O(n)$。有沒有辦法優化呢？是可以的，如果用一個提供新增並且可以快速求前綴和資料結構來當作$D[i]$，就可以降下worst case的時間複雜度，但這題的參數範圍實在不需要這麼做，我們就留給有興趣的讀者自行嘗試了。
```python=
class Solution:
# num of LIS
# D[i] = (p,f) LIS of length i ending with p of frequency f
def findNumberOfLIS(self, nums: List[int]) -> int:
last = [-1000001]
D = [[(-1000001,1)]]
for x in nums:
i = bisect_left(last,x)
num = sum(f for p,f in D[i-1] if p<x)
if i>=len(D):
D.append([(x,num)])
last.append(x)
else:
D[i].append((x,num))
last[i] = x
ans = sum(f for p,f in D[-1])
return ans
```
[(題目連結) 898. Bitwise ORs of Subarrays (Medium)](https://leetcode.com/problems/bitwise-ors-of-subarrays/)
給一個非負整數的陣列$arr$，請問所有可能子陣列的bitwise OR的結果有多少種。陣列長度$\leq 5\times 10^4$，數字範圍$\leq 10^9$。
如果把全部的$O(n^2)$個子陣列全部弄出來，每個子陣列還要花$O(n)$的時間做OR，整體時間複雜度跑到$O(n^3)$。如果把所有固定左端的一起做，會好一點，對右端$i$，從$i$到$0$嘗試左端，每次多OR一個數字，這樣整體時間複雜度降到$O(n^2)$還是太慢。
從DP的想法，假設$S[i]$是所有右端在$i$的子陣列的結果，來考慮從$S[i-1]$如何計算$S[i]$。跟Max Subarray的思考方式類似，$i$結尾的的子陣列就分兩種：只有$arr[i]$本身，以及所有$i-1$結尾的子陣列在多延伸一個到$i$。所以
$$
S[i] = \{ arr[i] \text{ OR } x: \text{ for } x\in S[i-1]\}\cup \{arr[i]\}
$$
因為相同的不能重複計算，用set()來做是最合適了。
以下是範例程式。我們用兩個set()，$result$用來存所有的結果，而$suffix$存目前以$i$結尾的所有結果。第8 ~ 10行歷遍所有整數，每次先更新$suffix$，再納入$result$。
這個程式很簡單，但疑問是時間複雜度可以嗎？是多少呢？如果$suffix$的大小每走一步多一個，那不就糟糕了嗎？
事實上它不會太大，最多只有32個，範例程式的註解裡面有解釋。所以時間複雜度是$O(n)$，或者說$O(n\log R)$，其中$R$是整數上限。
```python=
class Solution:
# sweep forward, when sweep to i, keep all possible
# result of any suffix [j:i] in a set
# suffix is small since [j-1:i] is either same as [j,i] or
# at least one more bit than [j:i]
def subarrayBitwiseORs(self, arr: List[int]) -> int:
result,suffix = set(),set()
for p in arr:
suffix = {p|x for x in suffix} | {p}
result |= suffix
return len(result)
```
**Weighted activity selection problem**
[(題目連結) 1235. Maximum Profit in Job Scheduling (Hard)](https://leetcode.com/problems/maximum-profit-in-job-scheduling/)
每個工作需要一個指定的時間的連續區間，可以獲得若干酬勞，要挑選不重疊的工作獲取最大的酬勞總和，端點可以重疊。$n\leq 5\times 10^4$，時間$\leq 10^9$。
問題是要挑選權重總和最大且互相不重疊的線段，這個問題也稱為weighted activity selection problem，如果權重都一樣，就是要挑選最多活動，那可以用貪心法則來求解：挑選最早結束的活動就對了。
但是在本題加權版本時，挑最早結束的是錯的，挑權重最大的也是錯的。放棄貪心來試試DP。
將所有工作根據結束時間重新編號，我們企圖由小到大依序計算第$i$個工作結束的時間點可以獲得的最大利益$p[i]$。有兩種選擇：
* 第$i$個工作不挑，$p[i]=p[i-1]$；
* 第$i$個工作有挑，$p[i]=p[j]+\text{profit of } i$，其中$j$是在$i$開始前(含)最後一個結束的工作。
因為工作已經依照結束時間重新排序，我們可以用二分搜來找開始前的最後一個工作。以下是範例程式。第5行將工作排序，結束時間放在第一欄位，因此是依照結束時間由小到大。第6行$d$是用來存結束時間，$p$則是存最大利益。一開始放0(不可能的小)當做哨兵來簡化邊界條件，如此一來每個工作都存在開始前的工作。
進入迴圈時，先以二分搜找前置工作的編號$i$，bisect_right是找第一個大於的位置，再減1就是小於等於了，接著把新獲得的結束時間與最大獲利放入。最後的答案在最後一項$p[-1]$。時間複雜度$O(n\log n)$，因為排序以及做了$n$次二分搜。
```python=
class Solution:
# activity selection
def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
n = len(profit)
job = sorted([(endTime[i],startTime[i],profit[i]) for i in range(n)])
d,p = [0],[0] # (finish time, max profit)
for f,s,k in job:
i = bisect_right(d,s)-1 # <=startTime
d.append(f)
p.append(max(p[-1],k+p[i]))
return p[-1]
```
## 結語
這個單元介紹DP的基本原理與一維的題型，一維DP還有一個重要的題型是：DP+單調隊列，這題型已在[Python-LeetCode 581 第10招 單調隊列 Monotonic stack and deque](/DY_JORzKQg6rgXM0HZX-0Q)中舉了兩例說明，有興趣的讀者請自行前往該單元參考LeetCode 1425與1696。
下個單元將介紹其他的DP形式。
Sign in with Wallet
Connect another wallet