---
title: 分治法 Divide and Conquer & 動態規劃 Dynamic Programming
tags: 講義
---
分治 & 動態規劃
===
:::spoiler 目錄
[TOC]
:::
---
這兩者不算演算法，更像是一種想法
精神：原問題切割成子問題 >> 子問題的答案組成原問題的答案
# 分治法 Divide and Conquer
>分而治之：
>把大問題分解成小問題，小問題解決後，整個問題就解決了
>
>問題具有重複性質（可遞迴）
>子問題彼此獨立
## 步驟
* 分解 Divide：將原問题分解成與原問題相似，規模較小的子問题
* 解決 Conquer：解決各個子問题（迭代或遞迴），若子問题夠小，則直接求解
* 合併 Combine：將子問题的结果合併成原問题的解
## 迭代 和 遞迴 之比較
* 迭代 iterative：
```
用 for 迴圈重複執行相同的計算
```
* example：
```cpp
int sum(int n){
int s = 0 ;
for(int i = 0; i < n; i ++)
s += i ;
return s ;
}
```
* 遞迴 recursive：
```
1. 重複呼叫自身函式
2. 要有 "終止條件"，否則會陷入無限迴圈
```
* example：
```cpp
int sum(int n){
if(n == 1)// 終止條件
return 1 ;
else
return sum(n - 1) + n ;// 遞迴關係式：S(n) = S(n - 1) + n
}
```
* 可讀性：遞迴 > 迭代
* 可改性：遞迴 > 迭代
* 簡潔度：遞迴 > 迭代
* 時間效率：遞迴 < 迭代
* 記憶體$^*$效率：遞迴 < 迭代
* 遞迴：每多呼叫一次就要多用一個記憶體
* 迭代：每次的局部變數都用同一個記憶體
* 遞迴需用到 stack$^*$ >> 有呼叫上限
* 註：
* 一個函式拿到記憶體後大概會分成這樣：
* 如果一直重複呼叫函式，就會一直用到 stack，最後用到其他區塊，這就叫"stack overflow" ~~如果程式不會寫，stackoverflow!!~~
* 實例比較：
* Fibonacci Sequence
* 分治（遞迴）：
```cpp
int fib(int n){
return n <= 2 ? 1 : fib(n - 1) + fib(n - 2) ;
}
```
時間複雜度：$Ｏ(n^2)$
* DP：
```cpp
int fib(int n){
int dp[INT_MAX] ;
dp[0] = 1 ;
dp[1] = 1 ;
for(int i = 2; i < n; i ++)
dp[i] = dp[i - 1] + dp[i - 2] ;
return dp[n - 1] ;
}
```
時間複雜度：$Ｏ(n)$
## 例題
* 給定長度為 $n$ 的序列，求最大連續數組和
*
# 動態規劃 Dynamic Programming, DP
>將問題分解成一系列重疊子問題
>儲存中間計算結果避免重複計算
>
>最佳子結構：全局最佳解可以通過選擇每個子問題的最佳解來獲得。
>重疊子問題：子問題彼此相關
## 步驟
* 定義 DP 陣列
* 陣列所代表的意義
* 找出轉移式
* 轉移式：
* 狀態間的關聯
* 類似遞迴關係式
## 前綴和
* 現有一數列 <$a_n$> = $a_1$, $a_2$, $a_3$, $a_4$ ...
* 定義另一數列 <$S_n$>
$S_1$ = $a_1$
$S_2$ = $a_1$ + $a_2$
$S_3$ = $a_1$ + $a_2$ + $a_3$
... ...
$S_n$ = $a_1$ + $a_2$ + $a_3$ + ...... + $a_n$
* 此數列就是 <$a_n$> 之前綴和
* 轉移式為：$S_i$ = $S_i$$_-$$_1$ + $a_i$
* $S_i$ 是由 $S_i$$_-$$_1$ 決定，因此稱 $S_i$$_-$$_1$ 為 $S_i$ 的“轉移點”
* 作用：
* $a_i$ + ...... + $a_j$ = ($a_1$ + ...... + $a_i$$_-$$_1$) + ($a_i$ + ...... + $a_j$) - ($a_1$ + ...... + $a_i$$_-$$_1$) = $S_j$ - $S_i$$_-$$_1$
## 技巧--滾動優化
>減少記憶體使用
>只儲存所需的最少資料
* 比如費氏數列的轉移式為：$A_n$ = $A_n$$_-$$_1$ + $A_n$$_-$$_2$
每項只和前兩項有關係，所以只要保留 3 項就好
:::spoiler 程式碼
```cpp
int fib(int n){
int f[3] ;
f[0] = 1 ;
f[1] = 1 ;
for(int i = 2; i < n + 2; i ++){
// 因為每次的f[2]都是第 i - 1 項
// 所以 i = n + 1 時 f[2] 才會是第 n 項
f[0] = f[1] ;
f[1] = f[2] ;
f[2] = f[0] + f[1] ;
}
return f[2] ;
}
```
:::
## 題目
>其實很多問題都可以用 DP 來解，常見的經典問題包含但不限於：路徑問題、最長共同子序列、LIS、LCS、背包問題等，另外還有最佳化問題和計數問題等。
### 背包問題
>背包問題是動態規劃的經典題型之一
>給定背包大小、物品重量和價值，在限定重量內使物品總價值最高。
>按條件可分為：
> 1. 0-1 背包問題--每種物品只有一個
> 2. 無限背包問題--每種物品有無限個
> 3. 有限背包問題--每種物品有有限個
1. **0-1 背包問題**
* 有 $N$ 個物品，第 $i$ 個物品重量為 $w_i$，價值為 $v_i$，背包容量為$W$，求背包內物品的最大價值總和 $(N \le 100,\,w_i \le W \le 10^5,\,v_i \le 10^9\,)$。
* DP 定義：
* $dp[\,i\,][\,j\,]$：考慮前 $i$ 個物品，重量為 $j$ 時的最大價值和
* 找出轉移式：
* 假設已處理前 $i-1$ 個物品的所有狀態(不同重量)，對於下一個物品可以選擇取或不取
* 取：重量由 $j-w_i$ 變為 $j$，價值增加 $v_i \to dp[\,i\,][\,j\,]=dp[\,i-1\,][\,j-w[\,i\,]\,]+v[\,i\,]$
* 不取：重量、價值皆不變 $\to dp[\,i\,]=dp[\,i-1\,][\,j\,]$
* 轉移式：$dp[\,i\,][\,j\,]=\max(dp[\,i-1\,][\,j\,],\,dp[\,i-1\,][\,j−w[\,i\,]\,]+v[\,i\,]\,)$
* 空間優化：
* 因為 $dp[\,i-1\,][\,j\,]$ 和 $dp[\,i-1\,][\,j-w[\,i\,]\,]$ 只會影響 $dp[\,i\,][\,j\,]$，再來不會用到，因此可以用滾動優化的方式，將$dp[\,i-1\,][\,j\,]$ 用 $dp[\,i\,][\,j\,]$ 覆蓋
* 推得第二轉移式為：$dp[\,j\,]=\max(dp[\,j\,],\,dp[\,j-w[\,i\,]\,]+v[\,i\,]\,)$
:::spoiler 程式碼
```cpp
void sol(){
cin >> N >> W ;
for(int i = 1; i <= N; i ++)
cin >> w[i] ;
for(int i = 1; i <= N; i ++)
cin >> v[i] ;
for(int i = 1; i <= N; i ++)
// 先遍歷物品：因為是對物品選擇取或不取來決定重量
for(int j = W; j >= w[i]; j --)
// j >= w[i]：若 w[i] > j 顯然放不下
// 重量(j)由大到小遍歷：因為每個物品只能取一次，這樣是為了確保 dp[j] 是由 dp[j - w[i]] 推得
dp[j] = max(dp[j - w[i]] + v[i], dp[j]);
cout << dp[W] << "\n" ;
}
```
:::
2. **無限背包問題**
* 有 $N$ 種物品，第 $i$ 個物品重量為 $w_i$，價值為 $v_i$，背包容量為$W$，求背包內物品的最大價值總和。($N$ <= $100$, $w_i$ <= $W$ <= $10^5$, $v_i$ <= $10^9$)
* DP 和 轉移式 都和 0-1 背包問題一樣，但是不同的是無限背包問題可以重複放入
* 在 0-1 背包問題中，為了確保只取一次，重量由大到小遍歷，這裡只要考慮最大值即可，所以改成由小到大
:::spoiler 程式碼
```cpp
void sol(){
cin >> N >> W ;
for(int i = 1; i <= N; i ++)
cin >> w[i] ;
for(int i = 1; i <= N; i ++)
cin >> v[i] ;
for(int i = 1; i <= N; i ++) // 遍歷物品
for(int j = w[i]; j <= W; j ++) // 遍歷重量
dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
cout << dp[W] << "\n" ;
}
```
:::
3. **有限背包問題**
* 有 $N$ 種物品，第 $i$ 個物品有 $n_i$ 個，重量為 $w_i$，價值為 $v_i$，背包容量為$W$，求背包內物品的最大價值總和。($N$ <= $100$, $w_i$ <= $W$ <= $10^5$, $v_i$ <= $10^9$)
* 這也可以用 0-1 背包的方式做，把 $n$ 個物品看成能取 $n$ 次就好
:::spoiler 程式碼：
```cpp
void sol(){
cin >> N >> W ;
for(int i = 1; i <= N; i ++)
cin >> n[i] ;
for(int i = 1; i <= N; i ++)
cin >> w[i] ;
for(int i = 1; i <= N; i ++)
cin >> v[i] ;
for(int i = 1; i <= n; i ++) // 遍歷物品
for(int k = 0; k < n[i];k ++) // 遍歷次數
for(int j = W; j > w[i]; j --) // 遍歷重量
dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
cout << dp[W] << "\n" ;
}
```
:::
* 優化：
* $1$, $2$, $2^2$, $2^3$ , ..., $2^n$ 可以組成 $2^n - 1$ 以內的任何正整數
* 證明：$17_($$_1$$_0$$_)$ = $10001_($$_2$$_)$
* 意義：$17$ = $2^0$ x $1$ + $2^1$ x $0$ + $2^2$ x $0$ + $2^3$ x $0$ + $2^4$ x $1$
* $17$ = $1$ + $0$ + $0$ + $0$ + $16$
* 所以只要把 $n$ 拆成 $2$ 的冪次，就可以變成 log $n$ 個，也降低了時間複雜度
### LIS
>最長嚴格遞增子序列 Longest Increasing Subsequence
>子序列：從原序列取幾個元素按原相對位置排序而形成的新序列
* 給定一個長度為 $n$ ( $1$ ≤ $n$ ≤ $10^5$ ) 的序列 <$A_n$> 請問這個序列的 LIS 長度是多少?
* $O(n^2)$：
* DP 定義：
* dp[ $i$ ]：以 $A_i$ 結尾的 LIS 長度
* 找出轉移式：
* 令 <$S_i$> 為 以 $A_i$ 結尾的 LIS
* 一開始每個 <$S_i$> 長度都是 $1$
* 當 $j$ < $i$ 時，如果 $A_j$ < $A_i$，代表 <$S_i$> 可以接在 <$S_j$> 後面
* 因此轉移式：
* dp[ $i$ ] = max( dp[ $j$ ] + $1$ ) ∀ $i$ > $j$ ∧ $A$[ $i$ ] > $A$[ $j$ ]
* 每個嘗試的前提都是 <$S_i$> 長度都是 $1$(還沒接任何數列)
:::spoiler 程式碼：
```cpp
void sol(){
cin >> n ;
for(int i = 1; i <= n; i ++)
cin >> a[i] ;
for(int i = 1; i <= n; i ++)
dp[i] = 1 ;
for(int i = 1; i <= n; i ++)
for(int j = 1; j < i; j ++)
if(a[i] > a[j])
dp[i] = max(dp[i], dp[j] + 1);
int ans = 0 ;
for(int i : dp)
ans = max(ans, i);
cout << ans << "\n" ;
}
```
:::
* 顯然，$O(n^2)$ 太慢了
* $O(nlogn)$：
* 設現在有一個 Fake LIS 陣列 (FLIS)，裡面的元素遞增，那要做的事情就是依序將 $A$[ $1$ ], ..., $A$[ $n$ ] 放進這個 FLIS 裡面。
* $i$ 從 1 到 $n$
* 迭代器 it 尋找 FLIS 中第一個不小於 $A$[ $i$ ] 的元素
* 如果 it 等於 FLIS.end()：
* $A$[ $i$ ] 大於 FLIS 中的所有元素
* 將 $A$[ $i$ ] 添加到 FLIS 尾端
* 如果 it 不等於 FLIS.end()：
* FLIS 中存在一個大於等於 $A$[ $i$ ] 的元素
* *it (it 所指的元素) 要換成 $A$[ $i$ ]，這樣可以再添加更多元素
* 遍歷完所有 <$A_n$> 的元素後，LIS 的長度等於 FLIS 的大小
* FLIS 並不是真的 LIS，是各位置上 IS 的最佳解
:::spoiler e.g
A = {1, 4, 2, 8, 5, 7, 4, 8, 7, 6, 3}
> FLIS：1
> FLIS：1, 4
> FLIS：1, 2
> FLIS：1, 2, 8
> FLIS：1, 2, 5
> FLIS：1, 2, 5, 7
> FLIS：1, 2, 4, 7
> FLIS：1, 2, 4, 7, 8
> FLIS：1, 2, 4, 7, 8
> FLIS：1, 2, 4, 6, 8
長度：5
:::
:::spoiler 程式碼：
```cpp
void sol(){
cin >> n ;
for(int i = 1; i <= n; i ++)
cin >> a[i] ;
vector<int> FLIS;
for(int i = 1; i <= n; i ++){
auto it = lower_bound(FLIS.begin(), FLIS.end(), a[i]);
if(it == FLIS.end())
FLIS.push_back(a[i]);
else
*it = a[i] ;
}
cout << FLIS.size() << "\n" ;
}
```
:::
### LCS
## 其他例題
* 線性 DP：
* 有 $n$ $(1 ≤ n ≤ 10^5)$ 顆石頭，第 $i$ 顆石頭的高度為 $h_i$。 有一隻青蛙一開始站在第 1 顆石頭上，他想要跳到第 $n$ 顆石頭。 假設青蛙當前站在第 $i$ 顆石頭上，則它可以選擇跳往第 $i + 1$ 顆石頭或第 $i + 2$ 顆石頭。如果他決定會跳往第 $j$ $(j = i + 1$ or $i + 2)$ 顆石頭，會花費他 $|h_i−h_j|$ 點體力。 請問青蛙最少需要花費多少點體力才能跳到第 $n$ 顆石頭上。
1. 定義陣列：
* dp[ $i$ ]：從第 1 顆石頭跳到第 $i$ 顆石頭所需花費的最少體力。
* 所求 = dp[ $n$ ]
2. 找出轉移式：
* 可從第 $x$ 顆跳到第 $x + 1$ 顆或第 $x + 2$ 顆，即：跳到第 $x$ 顆可從第 $x - 1$ 顆或第 $x - 2$ 顆出發。
* dp[ $i$ ] = min(dp[ $i - 1$ ] + | $h_i$ - $h$$_i$$_-$$_1$ |, dp[ $i - 2$ ] + | $h_i$ - $h$$_i$$_-$$_2$ | )
* 特殊情況：dp[ $1$ ] = $0$ , dp[ $2$ ] = | $h_1$ - $h_2$ |
:::spoiler 程式碼：
```cpp
void sol(){
cin >> n ;
for(int i = 1; i <= n; i ++)
cin >> h[i] ;
dp[1] = 0 ;
dp[2] = abs(h[1] - h[2]) ;
for(int i = 3; i <= n; i ++)
dp[i] = min(dp[i - 1] + abs(h[i] - h[i - 1]), dp[i - 2] + abs(h[i] - h[i - 2]))
cout << dp[n] << "\n" ;
}
```
:::
* 二維 DP：
* 有一隻螞蟻在四面體上爬，它可以沿著邊從一個頂點走到另外三個頂點，請問有幾種走法可以讓螞蟻從頂點 D 出發走 $n$ $(n ≤ 10^7)$ 步後回到頂點 D。 由於數字可能很大，請將答案 $mod$ $10^9 + 7$ 之後輸出。
1. 定義陣列：
* dp[ $i$ ] [ $j$ ]：走 $i$ 步後，站在 $j$ 點的方法數。
* 因為只有四個頂點，所以 $j$ 只會有 $4$ 個，我定為 $0$, $1$, $2$, $3$
* 所求：走 $n$ 步回到頂點 >> dp[ $n$ ] [ $0$ ]。
2. 找出轉移式：
* 上一步一定是從其他點走過來，所以把上一步站在其他點的方法數加總就是這一步站在這一點的方法數。
* dp[ $i$ ] [ $0$ ] = dp[ $i − 1$ ] [ $1$ ] + dp[ $i − 1$ ] [ $2$ ] + dp[ $i − 1$ ] [ $3$ ]
* dp[ $i$ ] [ $1$ ] = dp[ $i − 1$ ] [ $0$ ] + dp[ $i − 1$ ] [ $2$ ] + dp[ $i − 1$ ] [ $3$ ]
* dp[ $i$ ] [ $2$ ] = dp[ $i − 1$ ] [ $0$ ] + dp[ $i − 1$ ] [ $1$ ] + dp[ $i − 1$ ] [ $3$ ]
* dp[ $i$ ] [ $3$ ] = dp[ $i − 1$ ] [ $0$ ] + dp[ $i − 1$ ] [ $1$ ] + dp[ $i − 1$ ] [ $2$ ]
:::spoiler 程式碼：
```cpp
void sol(){
int MOD = 1e9 + 7 ;
cin >> n ;
dp[0][0] = 1 ;
for(int i = 1; i <= n; i ++){
dp[i][0] = (dp[i - 1][1] + dp[i - 1][2] + dp[i - 1][3]) % MOD ;
dp[i][1] = (dp[i - 1][0] + dp[i - 1][2] + dp[i - 1][3]) % MOD ;
dp[i][2] = (dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][3]) % MOD ;
dp[i][3] = (dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2]) % MOD ;
}
cout << dp[n][0] << "\n" ;
}
```
:::
# 分治 和 DP 之比較
| | 分治 | DP |
|-|-|-|
|子問題彼此關聯|否|是|
|儲存每個子問題的答案|否|是|
Sign in with Wallet
Connect another wallet