# DP 定義
紀錄已經解決的問題的答案，避免重複計算，用舊有的資訊快速計算新資訊，並且分為兩種方式
1. Buttom-Up (由底層慢慢往上推論計算)
2. Top-Down (由上層慢慢往下推論計算)
先來看一個例子
## 費氏數列
所以可以用上面 Array 的方式儲存省略計算
```python=
# python
def fas(n) :
if n == 0 : return 0
if n == 1 : return 1
if (dp[n] == 0) : dp[n] = fas(n-1) + fas(n-2)
return dp[n]
```
```cpp=
// c++
int dp[10005] = {} ; // 注意初始化陣列才能讓所有元素變成0
int fas(int n) {
if (n == 0) return 0 ;
if (n == 1) return 1 ;
if (dp[n] == 0) dp[n] = fas(n-1) + fas(n-2) ;
return dp[n]
}
```
計算: 時間複雜度: $O(n)$
查詢: 時間複雜度: $O(1)$
用途: 在需要多次查詢費是數列的結果時可以使用這種方式
### 費氏數列延伸-走樓梯問題
第一題是很經典的爬樓梯問題，當你一次只能走一步，或是走兩步的情況下，有多少種方式可以爬到 n階 的階梯？
我們先一個一個看，找出規律：
* f(1) = 1 (一步)
* f(2) = 2 (一步+一步 or 兩步)
* f(3) = 3 (一步+一步+一步 or 一步+兩步 or 兩步+一步)
* f(4) = 5 (1+1+1+1 or 1+1+2 or 1+2+1 or 2+1+1 or 2+2)
## DP 的本質-有向無環圖的最短路
一張有向無環圖，有 n 個節點，無數的邊，問某點 N1 到某點 N2 的最短路徑
簡單來說，你可以去找 N1 到所有點的最短路，然後就可以推出到 N2 的最短路了
其實就是在到達某點的時候，可以判斷這個點能前往的點是否有更短的路徑
```cpp=
int short_to_x(int x) {
if (visited[x]) return shortest[x] ; // 已經走過的"目前"最短路
visited[x] = true ;
if (x == destination) shorted[x] = 0 ; // 終點
else {
shortest[x] = MAX_INT ; // 假設為最大距離
for (auto out: next[x]) { // 找所有出邊
int dis = short_to_x(out.node) + out.w ; // 試試看新路線
if (dis < shortest[x]) shortest[x] = dis ;
}
}
return shortest[x] ;
}
void DAG() {
for (int i=1;i<=n;i++) { // 把任意點當成 N1
short_to_x(i) ;
}
}
```
總而言之，動態規劃只要找好抽象化的部分
就可以得到一個有向無環圖(也可以說是一個拓樸排序)
## Top-Down v.s Bottom-Up
### Top_Down的優缺點
優點
* 轉移式很直覺(把算過的結果儲存就好)
缺點
1. pass by value && pass by reference(傳值、傳址差異)
2. stack overflow(python內建限制1000層)
3. 時間複雜度的常數很大(看不出來但會影響執行速度)
### Bottom-Up的優缺點
優點
* 寫起來很乾淨
缺點
* 轉移式比較難想到
## 組合題-骰子問題
* 骰⼦有 1 ~ 6 點，現在可以骰無限顆骰⼦，依序骰每⼀個骰⼦
* 求最後共有幾種骰法會使所有骰⼦的點數和為 n
舉例 ：
○ n = 3 , 組合數 = 4
○ 1 + 1 + 1
○ 2 + 1
○ 1 + 2
○ 3
### 實際動態規劃步驟
第一步都是 **定義轉移式** ，轉移式有點類似 Function
這題我們定義轉移式 $dp[i] =$ 擲出骰子點數為 $i$ 的組合數量
因為骰子最多只能投到 6 點
所以要判斷 $dp[i]$ 的時候，要一次判斷前 6 個數字的組合數量
也就是 $dp[i] = dp[i-1] + dp[i-2] + ... + dp[i-6]$
如果還是不能理解的話，可以先用 7 當作例子
如果前面骰子總和是 1(也就是7-6)，那麼這時候只要再投出 6 點就會剛好是 7
對於 $i - 6$ 的情況來說， $dp[i] += dp[i-6]$
如果前面骰子總和是 2(也就是7-5)，那麼這時候只要再投出 5 點就會剛好是 7
其他點數以此類推，所以最後用一個迴圈就可以計算出結果
```python=
# python
mod = 10**9 + 7
n = int(input())
dp = [0] * (n+1)
dp[0] = 1
for i in range(1,n+1) :
for j in range(1,6+1) :
if (i-j >= 0) :
dp[i] += dp[i-j]
dp[i] %= mod
else : break
print(dp[n])
```
```cpp=
// c++
int mod = 1e9 + 7 ;
int main() {
int n ;
cin >> n ;
dp[0] = 1 ;
for (int i=1;i<=n;i++)
for (int k=1;k<=6;k++)
if (i-k >= 0) // 判斷i-1到i-6的組合數
dp[i] = (dp[i] + dp[i-k]) % mod ;
cout << dp[n] << '\n' ;
}
```
### 延伸問題-硬幣找零問題
硬幣找零問題可以有非常多版本，此版本的問題是給定 n 種硬幣
並且給定每個硬幣的面額 $C_i$，可重複選取同一種硬幣，
最後求找零總金額 x 的硬幣選法有幾種
比如要找零 $6$ 元，硬幣有 $2$ 種 ${1,3}$
找零的方式就有下列幾種
* (1,1,1,1,1,1)
* (1,1,1,3)
* (1,1,3,1)
* (1,3,1,1)
* (3,1,1,1)
* (3,3)
跟剛剛題目的思路很像，但是多了不固定的硬幣面額，所以我們可以用一個 Array 儲存面額
再來可以定義轉移式 $dp[i] =$ 總合為 $i$ 的硬幣選法有幾種
因為有未知的硬幣種類與面額，Array的長度(硬幣種類數量)跟內容(各硬幣面額)很重要
對於 $i-C_1$ 來說，只要再一個 $C_1$ 就可以湊到 $i$
對於 $i-C_2$ 來說，只要再一個 $C_2$ 就可以湊到 $i$
後面以此類推，所以跟剛剛題目的原理一樣，只是硬幣變成 $C_1$~$C_n$
```python=
# python
n, m = map(int, input().split())
dp = [0] * (m+1)
money = list(map(int, input().split()))
dp[0] = 1
for i in range(1,m+1) :
for k in range(n) :
if (i-money[k] >= 0) :
dp[i] = (dp[i] + dp[i-money[k]]) % mod
print(dp[m])
```
```cpp=
// c++
int n, m ;
cin >> n >> m ;
vector <int> my(n) ;
for (int i=0;i<n;i++) cin >> my[i] ;
dp[0] = 1 ;
for (int i=1;i<=m;i++)
for (int k=0;k<n;k++)
if (i-my[k] >= 0) dp[i] = (dp[i]+dp[i-my[k]]) % mod ;
cout << dp[m] ;
```
## 選擇行動題-青蛙跳石頭
有一隻青蛙在山腳下，山路總共有 $n$ 個石頭，每一個石頭的高度為 $h_i$
這隻青蛙每次只能跳 1 或 2 顆石頭，並且它如果原本在高度 $a$ 的石頭想要跳到高度 $b$ 的石頭上
需要花費 $\vert a - b\vert$ 的體力，求青蛙跳到第 $n$ 個石頭所需要的**最少體力花費**
解題思路 :
這題相較於前兩題沒有這麼直觀了，但是依然可以從題目得知
跳到第 $i$ 個石頭的可能只有兩種，就是從 $i-1$ or $i-2$ 個石頭跳過去
所以只要能算到 $i-1$ ans $i-2$ 兩個石頭的最少體力花費，就可以算出第 $i$ 個石頭
定義轉移式 $dp[i] =$ 跳到第 $i$ 個石頭最少體力花費
青蛙初始位置在 $i=1$，所以 $dp[1] = 0, dp[2] = \vert h_1 - h_2\vert$
因為剩下的石頭都有 $i-1$ or $i-2$ 兩個可能，所以要找出最小花費的方案
如果第 $i-2$ 個石頭高度是 $a$，第$i-1$ 個石頭高度是 $b$
所以要找 $min(dp[i-2]+\vert a-h_i\vert, dp[i-1]+\vert b-h_i\vert)$
```python=
# python
dp = [0] * (n+1)
h = list(map(int, input().split()))
dp[1] = 0
dp[2] = abs(a[2]-a[1])
for i in range(3,n+1) :
dp[i] = min(dp[i-1]+abs(h[i]-h[i-1]),
dp[i-2]+abs(h[i]-h[i-2]))
print(dp[n])
```
```cpp=
// c++
vector <int> h(n+1), dp (n+1, (int)1e9) ;
for (int i=1;i<=n;i++) cin >> a[i] ;
dp[1] = 0, dp[2] = abs(a[2]-a[1]) ;
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' ;
```
## 選擇行動題-放暑假
小沐放暑假只會做三件事
1. coding(寫程式)
2. eating(吃水餃)
3. sleeping(睡覺)
已知 :
如果在第 $i$ 天做第 $1$ 件事情小沐會得到 $a_i$ 的快樂度
如果在第 $i$ 天做第 $2$ 件事情小沐會得到 $b_i$ 的快樂度
如果在第 $i$ 天做第 $3$ 件事情小沐會得到 $c_i$ 的快樂度
並且小沐不會連續兩天做同一件事情，如果暑假有 $n$ 天
小沐在各種規劃下，她的快樂度最大是多少
解題思路 :
首先我們先整理題目的資訊，因為每一天都有 $3$ 種選擇
所以在第 $n$ 天的數據就會有 $3$ 個，跟之前的骰子、硬幣不同
在第 $i$ 天做第 $k$ 件事情不會在快樂度上影響到第 $i+1$ 天
也就是說不能用一維 Array 去儲存快樂值，而是用二維陣列儲存
最後定義移轉式 : $dp[i][k] =$ 第 $i$ 天做第 $k$ 件事情能得到的最大快樂度
(這是第一次使用二維移轉式，可能會比較有問題，多注意)
由移轉式得知 : $dp[1][1] = a_1,\ dp[1][2] = b_1,\ dp[1][3] = c_1$
(這裡先試試看做題，之後再看看情況講解)
因為不能連續兩天做同一件事情，所以我們在判斷的時候要記得
$dp[i][k_1] = max(dp[i-1][k_2],\ dp[i-1][k_3]) + a_1$
其他兩個移轉式以此類推
```python=
# python
a = [[0]*4 for i in range(10005)]
n = int(input())
for i in range(1,n+1) :
for j in range(1,4) :
a[i][k] = int(input())
dp[1][1] = a[1][1]
dp[1][2] = a[1][2]
dp[1][3] = a[1][3]
for i in range(2,n+1) :
dp[i][1] = max(dp[i-1][2], dp[i-1][3]) + a[i][1]
dp[i][2] = max(dp[i-1][1], dp[i-1][3]) + a[i][2]
dp[i][3] = max(dp[i-1][1], dp[i-1][2]) + a[i][3]
print(max(dp[n][1],dp[n][2],dp[n][3]))
```
```cpp=
// c++
int a[10005][4] ;
int n ;
cin >> n ;
for (int i=1;i<=n;i++)
for (int k=1;k<=3;k++)
cin >> a[i][k] ; // 會從index1開始是因為好理解
dp[1][1] = a[1][1], dp[1][2] = a[1][2], dp[1][3] = a[1][3] ;
for (int i=2;i<=n;i++) {
dp[i][1] = max(dp[i-1][2], dp[i-1][3]) + a[i][1] ;
dp[i][2] = max(dp[i-1][1], dp[i-1][3]) + a[i][2] ;
dp[i][3] = max(dp[i-1][1], dp[i-1][2]) + a[i][3] ;
}
cout << max(dp[n][1],dp[n][2],dp[n][3]) << '\n' ;
```
時間複雜度為 : $O(n)$
## 路徑之和問題
在高中常見的排列組合數學題之一
就是問一個 $n\times m$ 的矩形左上到右下共有幾種可能的走法(只能往下或往右走)
我們學過的解法是第一行第一列都只有 $1$ 種可能，剩下都是左邊格子+上方格子
這個解法的最原始狀態應該是這樣表達的
* 因為要走到某個點只能往下或往右，所以只會從左方或上方的格子過來
* 所以目前格子的可能走法 = 上方格子可能走法 + 左方格子可能走法
* 而第一行(直、上下的)沒有左方的格子，所以等於上方格子可能走法
* 第一列(橫、左右的)沒有上方的格子，所以等於左方格子可能走法
這時候因為原點也只有一種可能走法，所以程式碼會像是這樣
```python=
n, m = map(int, input().split())
G = [[0]*m for i in range(n)]
G[0][0] = 1
for i in range(1, n) :
G[i][0] = G[i-1][0]
for j in range(1, m) :
G[0][j] = G[0][j-1]
for i in range(1, n) :
for j in range(1, m) :
G[i][j] = G[i-1][j] + G[i][j-1]
print(G[n-1][m-1])
```
```cpp=
int n, m ;
cin >> n >> m ;
vector<vector<int>> G(n, vector<int> (m, 0)) ;
G[0][0] = 1 ;
for (int i=1;i<n;i++)
G[i][0] = G[i-1][0] ;
for (int j=1;j<m;j++)
G[0][j] = G[0][j-1] ;
for (int i=1;i<n;i++)
for (int j=1;j<m;j++)
G[i][j] = G[i-1][j] + G[i][j-1] ;
cout << G[n-1][m-1] << '\n' ;
```
當然大部分題目不會這麼單純，我們可以先看一題求路徑和的
### d378. 最小路徑
[題目連結](https://zerojudge.tw/ShowProblem?problemid=d378)
解題思路 :
同樣也是從左上到右下，也是只能往右與往下，但求路徑總和最小，一樣先列出算式
* 終點格子最小路徑 = max(終點上方格子最小路徑, 終點左方格子最小路徑) + 終點格子值
* 那其實對於每一個格子也是與終點同樣的處理方式
* 唯第一行、列要做跟之前同樣的處理
```cpp=
#include<bits/stdc++.h>
using namespace std ;
int G[105][105] ;
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0) ;
int n, m, idx = 1 ;
while (cin >> n >> m) {
for (int i=0;i<n;i++) {
for (int j=0;j<m;j++) {
cin >> G[i][j] ;
if (i && j) // 非第一行或第一列
G[i][j] += min(G[i-1][j], G[i][j-1]) ;
else if (i) // j = 0 第一行(直、上下的)
G[i][0] += G[i-1][0] ;
else if (j) // i = 0 第一列(橫、左右的)
G[0][j] += G[0][j-1] ;
}
}
cout << "Case #" << idx << " :\n" ; // 第 idx 個測資
cout << G[n-1][m-1] << '\n' ; // 最右下
idx++ ;
}
return 0 ;
}
```
當然這種題目肯定也多大多數人來說不是很難，下一題才是新手感覺最難的題型
### 2182 . 幸運表格 (Lucky)
[題目連結](https://tioj.ck.tp.edu.tw/problems/2182)
解題思路 :
這題可以從任一點開始，只要超出表格範圍就結束
同樣只能向下或向右，問路徑總和最大為多少
如果照我們最開始的想法，從任一點開始做
這樣明顯很慢，時間複雜度為 $O(n^2 m^2)$
但是我們可以轉換一下想法，如果超出範圍是結束
是不是代表終點只可能是最右邊那一行 $A$ 跟最下方的那一列 $B$
這時候終點已經固定了，並且肯定比起點少
所以我們把路徑的順序轉換一下
現在起點為 $A$ 或 $B$，請問走到任一點的路徑總和最大可能為多少
確保路徑過程只能往上或往左(也就是只能往下與往右的顛倒)
這時候你再嘗試把運算式列出來
* 對於某一點 $X$ 來說，走到 $X$ 的路徑指可能是從右方或下方走過來
* 所以 $X$ 的最大路徑總和 = max($X$ 下方路徑總和, $X$ 右方路徑總和) + $X$ 的值
* 但對於最右方那一行來說，$X$ 只能從下往上走到，最大路徑總和 = $X$ 下方路徑總和 + $X$ 的值
* 對於最下方那一列來說，$X$ 只能從右往左走到，最大路徑總和 = $X$ 右方路徑總和 + $X$ 的值
```cpp=
#include<bits/stdc++.h>
using namespace std ;
int G[1002][1002], dp[1002][1002] ; // 多的空間會是 0
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0) ;
int m, n ;
cin >> m >> n ;
for (int i=0;i<m;i++)
for (int j=0;j<n;j++)
cin >> G[i][j] ;
// 由於全域變數的矩陣會讓元素都為 0
// 所以不需要把最下方(最右方)跟其他位置做區分
// 但這個習慣只適合用在競程，所以請自行判斷是否要使用
int ans = INT_MIN ;
for (int i=m-1;i>=0;i--) {
for (int j=n-1;j>=0;j--) {
dp[i][j] = max(dp[i+1][j], dp[i][j+1]) + G[i][j] ;
ans = max(ans, dp[i][j]) ;
}
}
cout << ans << '\n' ;
return 0 ;
}
```
## 0/1 背包問題
由前面的題目應該能比較清楚得知關於動態規劃的用法
所以我們進入 DP 最具代表性的問題之一 : 背包問題
* 屬於 NP-Hard(還沒有找到多項式時間內的解法，對新手來說不重要)
* 題目給定 $n$ 種物品，容量 $m$ 的背包
* 第 $i$ 的物品會佔據背包 $w_i$ 的容量，它的價值是 $v_i$
* 要求讓背包所有物品價值越高越好
定義移轉式 : $dp[i][k] =$ 表示考慮選擇要不要拿第 $i$ 個物品的情況下，背包容量 $k$ 能獲得的最大價值
對於 dp[i][k] 來說有拿與不拿兩種
如果拿了第 $i$ 個物品，並且目前背包只有 $k$ 的容量
則可以反推在選擇要不要拿第 $i-1$ 個物品時，最多能用的容量只有 $k-w_i$ (從後面往前推，比較難想)
* 因為拿了第 $i$ 個物品會佔據 $w_i$ 的容量
* 如果在第 $i-1$ 個物品時，用掉超過 $k-w_i$ 的容量，則不能拿取第 $i$ 個物品
最後得出要拿第 $i$ 個物品的移轉式為 :
$dp[i][k] = dp[i-1][k-w_i] + v_i$ (第 $i$ 個物品的價值)
當然還有不拿這個選項，如果不拿
反推在選擇要不要拿第 $i-1$ 個物品時，最多能用的容量就有 $k$
$dp[i][k] = dp[i-1][k]$ (第 $i$ 個物品的價值)
所以把拿跟不拿兩種可能的轉移式結合就是
$dp[i][k] = max(dp[i-1][k],\ dp[i-1][k-w_i] + v_i$ (第 $i$ 個物品的價值)
最後的答案就是 $dp[n][m]$，也就是說對於這個二維陣列
我們必須求出整個二維陣列對應的數值才能算出答案
而且要從 $i = 0$ 開始推，慢慢往上推出結果(Bottom-Up)
時間複雜度就是走過整個二維陣列 : $O(nm)$
```python=
for i in range(1,n+1) :
for k in range(1,m+1) :
if (k-w[i] >= 0) :
dp[i][k] = max(dp[i-1][k-w[i]] + v[i], dp[i-1][k])
else :
dp[i][k] = dp[i-1][k]
print(dp[n][m])
```
```cpp=
// c++
// 注意要 dp[0][1~m] = 0
for (int i=1;i<=n;i++) {
for (int k=0;k<=m;k++) {
// 選擇要不要拿第 i 個物品
if (k-w[i] >= 0) dp[i] = max(dp[i-1][k-w[i]] + v[i], dp[i-1][k]) ;
else dp[i][k] = dp[i-1][k] ;
}
}
cout << dp[n][m] << '\n' ;
```
### 延伸-同物品無限拿取的背包問題
跟0/1背包問題的敘述一樣，但是同物品可重複放入背包，也就是有無限多個物品，但一樣 $n$ 種
因為物品可以重複拿，所以之前定義的轉移式 $dp[i] =>$ 選擇要不要拿第 $i$ 個物品 失去作用
重新定義轉移式為 : $dp[i] =$ 背包容量為 $i$ 時，能得到的最大價值
因為在任何容量，只要體積(重量)沒爆，就能拿任一種物品
也就是說，在容量為 $i$ 的情況下有 m 種可能
* 前一個選擇結束耗費容量最多 $i-w_1$ 的情況下拿第 $i$ 個物品
* 前一個選擇結束耗費容量最多 $i-w_2$ 的情況下拿第 $i$ 個物品
後面以此類推，概念跟硬幣還有骰子很像(也是用for迴圈去跑過每種物品)
```cpp=
for (int i=1;i<=m;i++) {
for (int k=1;k<=n;k++) { // for迴圈去跑過每種物品
if (k-w[i] >= 0) dp[i] = max(dp[i], dp[i-w[k]] + v[k]) ;
}
}
cout << dp[m] << '\n' ; // 輸出容量 m 的最大價值
```
時間複雜度 : $O(nm)$
### 背包問題的瓶頸和優化-滾動陣列
時間複雜度根據NP-Hard問題所以很難改變
但空間複雜度似乎有很大的改進空間(除了無限背包 $O(m)$)
用 $n*m$ 的表格去紀錄(儲存)資料會有點太大了，空間複雜度是 $O(nm)$
這是因為DP是用 空間換時間的操作，如果 $n*m$ 太大，我們還是無法完成
這裡要介紹一個空間複雜度 $O(m)$ 的解法-**滾動陣列**
滾動陣列的核心概念就是 **沒用的空間重複使用**
從一般(有限)背包問題的轉移式 $dp[i][k] = max(dp[i-1][k], dp[i-1][k-w_i] + v_i)$
可以發現如果 $i = 7$ 的情況下，**只會**用到 $dp[i]$ 跟 $dp[i-1]$ 兩個陣列而已
也就是說 $dp[1\sim5]$ 完全不會用到，因為每一次計算只要用到上一次計算的結果
這時候就是滾動陣列出場的時候了
滾動陣列的實作要注意三點
1. 對於背包問題只會用到現在跟上一次的結果
2. 只要開兩個長度 $m$ 的陣列儲存資料
3. 這樣空間複雜度就從 $O(nm) -> O(m)$
這次一樣為了比較好理解把 Array 開成 $dp[2+1][m+1]$
用習慣或是理解後可以改成 dp[2][m] 就可以
至於使用兩個陣列的辦法就是判斷 $i$ 的奇偶
也就是 $dp[i\%2][k] = max(dp[(i-1)\%2][k],dp[(i-1)\%2][k-w_i] + v_i)$
那麼如果更進一步減少空間使用一維陣列呢 ?
因為結果可以一直使用不用特意清空，並且每次都是拿前一次的結果
這樣的概念可能會變成這種片段
```cpp=
// c++
for (int i=1;i<=n;i++)
for (int k=1;k<=m;k++)
if (k-w[i] >= 0) dp[k] = max(dp[k], dp[k-w[i]] + v[i]) ;
cout << dp[m] << '\n' ;
```
如果你帶入數字或是實際代測資跑過一遍就會發現有錯，我們用數字跑一次
假設我們在 $dp[5]$ 的時候拿了第 $i$ 個物品，這時候物品的體積是 $5$
結果到了 $dp[10]$ 的時候 : $dp[10] = dp[10-5] + v_i$
也就是說我們重複拿了第 $i$ 個物品，這樣就變成無限背包的解法了
問題就是因為 $k$ 較小的資訊更新會影響到 $k$ 較大的資訊
並且我們在更新資訊時**只要上一次的資訊**，那麼我們可以讓 $k$ 從 $m$ 跑回來
先處理 $k$ 較大的資訊就能避免被影響到，這樣就不會重複拿了
```cpp=
// c++
for (int i=1;i<=n;i++)
for (int k=m;k>=w[i];k--)
dp[k] = max(dp[k], dp[k-w[i]] + v[i]) ;
cout << dp[m] << '\n' ;
```
最後下一個總結，背包問題的變形其實有很多(下面會舉例)
並且比賽或題目遇到背包問題都會包裝得比較精美
### 變形-平分問題
* 現在已經很常見了，因為時代變遷(~~出題者沒創意~~)的關係
[d390. 00562 - Dividing coins](https://zerojudge.tw/ShowProblem?problemid=d390)
有 $m$ 個，每個硬幣的數值為 $a_i$，現在要把 $m$ 個硬幣分給兩個人
你的目標是要讓這兩個人拿到的數值總和差越小越好(就是兩個人要差不多錢)
先經過思考在看下面的詳解
解題思路 :
首先我們考慮到最完美的情況下，兩個人的總額應該都是 $sum(a) / 2$
這時候就可以題目理解成背包問題，給 $n$ 個物品，最大容量是 $sum(a) / 2$
每個硬幣的價值是 $a_i$，體積也是 $a_i$，求最多能裝入多少價值的硬幣
最後答案就是 $sum(a)\ -\ dp[sum(a) / 2]\ \times\ 2$
(注意不能使用 $sum(a) / 2\ -\ dp[sum(a) / 2]$ 因為會忽略奇數)
更詳細的說就是在 $dp[k]$ 能放多少錢，假如 $k = 6$ 但硬幣組合可能只有到 $5$
這時候 $dp[6] == 5$ 所以就是在 $k$ 為上限的情況下，能湊出的最大硬幣總額
### 延伸-有限背包問題
* 每種物品會有不同的數量 $num_i$
[參考講解](https://hackmd.io/@nehs-iced-7th/Hk9_m5KH_/https%3A%2F%2Fhackmd.io%2F%40Paul-Liao%2FSJHC9SE0u)
其他條件相同，問怎麼能獲得最大價值
解題思路 :
其實這跟 $0/1$ 背包問題一樣，只是可挑選物品數量變成 $\ge\ 1$
最直覺的想法就是多加一個迴圈跑過物品總數量
把多個同種物品當作 $num_i$ 個不同種物品，但是重量跟價值一樣
```cpp=
// c++
for (int i=1;i<=n;i++)
for (int j=0;j<num[i];j++) // 當作不同物品做處理
for (int k=m;k>=w[i];k--)
dp[k] = max(dp[k], dp[k-w[i]] + v[i]) ;
cout << dp[m] << '\n' ;
// 注意已經使用滾動陣列進行優化
```
這時候的複雜度會變成很抽象的樣子 $O(nm \times max(num))$
不過有更加抽象的方式可以進行優化(聽不懂就別說，需要較高數學能力)
---
二進制湊數字-使用迴圈跑過所有數字很直覺，但是用二進制跑出數字也可以
假設我要湊出 $6$ 以內的所有數字，使用 $(1,\ 2,\ 3)$ 就可以湊出來
* 1 = 1
* 2 = 2
* 3 = 3
* 4 = 1 + 3
* 5 = 2 + 3
* 6 = 1 + 2 + 3
也就是說，如果我們要解決總數量 $x$ 的物品，可以對 $x$ 做拆分
將 $x$ 拆分為 $(2^0,\ 2^1,\ 2^2,\ ...\ ,\ 2^p, q )$，$p$ 是使 $2^{p+1} - 1 \le x$ 的最大整數
而 $q = x - (2^{p+1} - 1)$，看起來有點抽象，我舉個例子幫助理解
假設 $x = 9$，因為 $2^3 = 8,\ 2^4 = 16$，所以此時的 $p$ 會是 $2$ (可以帶入上面的式子看看)
如果少了 $q$ 原本的 $(2^0,\ 2^1,\ 2^2)$ 最多總和是 $(1+2+4) => 7 => 2^3-1$
此時多了 $q$ 會是 $9-(2^{2+1}-1)\ ==\ 9-8+1\ ==\ 2$
所以 $q$ 的功用就是把數字湊起來的最後關鍵
* $(1+2+4)+2$ => $(2^0+2^1+2^2)+2$ => $9$ => $q = 2$
* $(1+2+4)+1$ => $(2^0+2^1+2^2)+1$ => $8$ => $q = 2$
這樣就可以不用用到 $2^3(8)$，還可以湊出 $8\sim15$ 的數字
所以原本要跑 $num_i$ 的程式，就可以變成最多$log_2(num_i) + 1$
此時的複雜度就會變成 $O(nm \times log(num))$
```cpp=
// c++
for (int i=1;i<=n;i++) {
int v, w, num, j ;
cin >> v >> w >> num ;
for(j=0;((1<<(j+1))-1)<=num;j++) { // 此時的 j 就是 p
int new_w = w<<j, new_v = v<<j ; // 根據數量不同的物品定義重量價值
for(int c=m;c>=new_w;c--) {
dp[c]=max(dp[c],dp[c-new_w]+new_v) ;
}
}
//
w = w*p-(w<<j)+w ; // 定義重量為剩餘數量 × 原始重量
v = v*p-(v<<j)+v ; // 價值也是
if(w) // 檢查是否還有剩餘的物品可以放入背包
for(int c=m;c>=w;c--)
dp[c]=max(dp[c],dp[c-w]+v) ;
}
cout << dp[m] << '\n' ;
// 已經使用二進位+滾動陣列進行優化
```
---
單調隊列解法(後面補上)
### 與有限背包概念相似的題目
給定 n 個硬幣，每個硬幣都有特定的⾯額(面額可重複但是不同硬幣)
請求出最⼩的⾯額，這⼀個⾯額是**不能**透過這 n 個硬幣湊出來的
範例輸入 :
5
2 9 1 2 7
範例輸出 :
6
解題思路 :
題目要求最小跟無法被給定硬幣湊出來兩個條件
從上述的範例輸出輸入來看，前 5 都能被湊出來
* 1 = 1, 2 = 2, 3 = 1 + 2, 4 = 2 + 2, 5 = 1 + 2 + 2
就最直觀的想法來說，湊硬幣除了要考慮到不同的組合，還要從最小的面額開始湊
那麼我們就可以先對硬幣面額大小做出排序，然後再繼續找規律
假設我們拿掉所有的 $2$，那麼最小值就會是 $2$，此時的硬幣是 $(1,7,9)$
假設保留一個 $2$，那麼最小值就是 $4$，此時的硬幣是 $(1,2,7,9)$
假設完全按這題目給定的範例，最小值是 $6$，此時的硬幣是 $(1,2,2,7,9)$
這時候會發現，第一種可能的答案是 $1$(第一個硬幣)$+1$，第二種可能是 $1+2$(前兩個硬幣和)$+1$
第三種可能的答案是 $1+2+2(前三個硬幣和)+1$，三個答案的共同點有兩個
1. 都要 $+1$
2. 在當前最大面額總和可能 $+1$ < 下一個硬幣面額大小 的時候，找到答案
也就是說，只要將硬幣排序完，再一一去判斷第二點，就能知道答案
```cpp=
int coin[5005] = {} ;
int main() {
int n ;
cin >> n ;
for (int i=0;i<n;i++) cin >> coin[i] ;
sort(coin,coin+n) ; // 排序硬幣面額
int total = 1 ; // 目前最大總和+1
for (int i=0;i<n;i++) {
if (total < coin[i]) break ; // 找到比總和+1更大的面額
total += coin[i] ;
}
cout << total << '\n' ;
}
```
## LIS-最長遞增子序列
所謂最長嚴格子序列就是在一個數值序列當中，找到最長的遞增(嚴格)數列
比如數列 : $A[4] = (1,3,2,4)$ 當中的 LIS 就是 $(1,3,4)$ 或 $(1,2,4)$
所以 LIS 不一定只有一個，通常題目會有限制某一個答案
先介紹時間複雜度 : $O(n^2)$ 的解法
定義移轉式 : $dp[i] =$ 表示結尾為 $A[i]$ 的 LIS 長度
LIS 需要從左到右去找出遞增序列，如果從移轉式的定義來看
$dp[1] = A[1]$ 因為子序列只有一個元素
那麼如果在求 $dp[4]$ 呢 我們要考慮到中間會有略過數字的可能
因為只是要求遞增的數列而已，所以可以看看前面數值跟 $dp[i]$ 的關係
如果 $dp[1] < dp[4]$ 那麼就可以將固定結尾為 $A[1]$ 的 LIS 後面接上 $A[4]$
如果 $dp[2] < dp[4]$ 那麼就可以將固定結尾為 $A[2]$ 的 LIS 後面接上 $A[4]$
後面以此類推，也就是說只要用迴圈跑過 $1$ ~ $i$ 就可以了
```cpp=
// c++
int A[5] = {0,1,3,2,4} ; // 方便理解多放一個空格
vector <int> dp(n+1,0) ; // 方便理解多放一個空格
dp[1] = 1 ;
int ans = 0 ;
for (int i=1;i<=n;i++) {
for (int k=1;k<=i;k++)
if (A[i] > A[k])
dp[i] = max(dp[i], dp[k] + 1) ;
ans = max(ans, dp[i]) ;
}
// 注意答案不是 dp[4]，dp[4] 是以 A[4] 當結尾的 LIS 長度
cout << ans << '\n' ;
```
如果我們害怕 TLE，有什麼辦法可以去縮小時間複雜度呢
(Robinson-Schensted-Knuth Algorithm)
(應該可以證明，但有點麻煩)
我們可以用兩個演算法搭配 DP 來輔助我們
1. 二分搜 Binary Search
2. 貪心演算法 Greedy Algorithm
我們額外開一個陣列 $B$，定義 $B[i]$ 為在 $i+1$ 長度的所有 LIS 中最小的結尾數值
我舉個例子來說明，假設現在長度為 $3$ 的 LIS 有 $(1,2,4)$, $(1,3,5)$, $(1,2,5)$, $(1,3,4)$
那麼這時候就會 $B[2] = 4$
如果這個數字能夠越小，表示整個 LIS 延續下去的可能越大(貪心)
跑過 $a[0]$ ~ $a[n-1]$，每次 $a[i]$ 可以被插入到 $B$ 中的哪個位置(二分搜)
假如 $B = (10,25,30)$，這時候 $a[i] = 12$，$B = (10,12,30)$
因為在長度為 $2$ 時，LIS 的最小結尾數值要選 $12$
也就是比較 $(10,25)$ 和 $(10,12)$
只要讓選擇的數值越小，後面在做 LIS 越輕鬆
假如 $B = (10,12,30)$，這時候 $a[i] = 45$，$B = (10,12,30,45)$
也就是有一個當前最大的數字可以放入
這時候要找出最長的 LIS，就要從 $B$ 的定義推論
$B[i]$ 是在 $i+1$ 長度的所有 LIS 中最小的結尾數值
也就是說，如果存在 $B[i]$，那麼就一定存在 $i+1$ 長度的 LIS
最後答案就是 $B$ 的長度
```cpp=
// c++
int solve(vector <int> a) {
vector <int> dp ; // 這裡的 dp 是 B
dp.push_back(-1e9) ;
for (int i=0;i<a.size();i++) {
auto it = lower_bound(dp.begin(),dp.end(),a[i]) ;
if (it == dp.end()) dp.push_back(a[i]) ;
else dp[it-dp.begin()] = a[i] ;
}
return dp.size() - 1 ; // 答案-1 是因為前面有插入一個最小值(才能進行第一次二分搜)
}
```
### d242. 00481 - What Goes Up
[題目連結](https://zerojudge.tw/ShowProblem?problemid=d242)
寫一個程式從一連串的整數序列中選出最長的嚴格遞增子序列（strictly increasing subsequence）
例如：$(1,3,2,2,4,0)$ 中最長的嚴格遞增子序列為 $(1,3,4)$ or $(1,2,4)$
解題思路 :
這題除了要求 LIS 的長度，還要求輸出其元素，所以只用上述的方法會無法達到輸出元素的要求
我們可以透過定義一個 Array $len$ : 元素 $a[i]$ 在 LIS 當中最後(數值最大)可能位置
舉個例子 $A = (1,3,2)$ 那麼 $B$ 就會從 $(1)$ -> $(1,3)$ -> $(1,2)$
而 $len = (1,2,2)$，這個意思就是說，$A$ 當中的 $1$ 在 LIS 中只能放到第 $1$ 位
如果 $A = (1,2,3)$ 那麼 $B$ 就會從 $(1)$ -> $(1,2)$ -> $(1,2,3)$
但是 $len = (1,2,3)$，因為此時 LIS 是 $(1,2,3)$，所以 A 當中的 $3$ 可以放到第 $3$ 位
由於題目還要求輸出最後方的 LIS，所以要從後方找出 LIS 元素
```cpp=
// c++
#include<bits/stdc++.h>
using namespace std ;
#define MAX 500005
int dp[MAX], len[MAX], a[MAX] ; // 用陣列比較快
int main() {
ios::sync_with_stdio(0) ; cin.tie(0) ; // 加速輸入
int i = 0, dplen = 0 ;
while (cin >> a[i]) {
// dplen 是最大 LIS 長度, i 是 a 長度
int l = 1, r = dplen, index = r+1 ;
while (l <= r) { // 二分搜
int mid = (l + r) / 2 ; // 中點
if (dp[mid] >= a[i]) r = mid - 1, index = mid ;
else l = mid + 1 ;
}
len[i] = index ; // 表示 a[i] 最多能放到 LIS 的甚麼位置
dp[index] = a[i++] ; // B 陣列
if (index > dplen) dplen = index ; // 比之前 LIS 更長
}
cout << dplen << "\n-\n" ;
int stklen = 0, stk[MAX] ;
// 因為要求相同長度 LIS 挑較靠右的(比較晚出現的)
// 所以要從後面找出在 LIS 同位置最靠右的元素
for (i--;i>=0 && dplen;i--)
if (len[i] == dplen)
stk[stklen++] = a[i], dplen-- ;
while (stklen)
cout << stk[--stklen] << '\n' ;
return 0 ;
}
```
### f608. 4. 飛黃騰達
[題目連結](https://zerojudge.tw/ShowProblem?problemid=f608)
飛黃是一種生物，活在二維座標平面上
有隻特別的飛黃一開始在座標 (0, 0) 的位置，而且你知道它只會往右上方移動
也就是移動的時只可以走到 $x$ 座標跟 $y$ 座標都不比原本小的位置
(所以 $nx \ge x\ \ \&\&\ \ ny \ge y$，不過程式中的位置應該是往右下)
現在座標平面的第一象限上有 n 個位置有果實，給定這 m 個果實的座標 (a, b)
你想要知道這隻特別的飛黃最多可以吃到幾個果實
（它必須移動到果實所在的座標才可以吃到果實）
解題思路 :
可能滿多人會有疑惑，以為要考慮到兩個參數的 LIS，其實沒有這麼誇張
我們回想一下 LIS 的定義，就是絕對嚴格遞增序列，但這題只需要要求 $\ge$
所以這裡要做出兩個想法上的改變
1. 因為可以 $\ge$，所以 lower_bound 改成 upper_bound
2. 因為可以 $\ge$，所以把某一個參數可以用 "排序"(省略 LIS)
根據這兩個想法，只要先用 $x$ 做排序，再對 $y$ 用 LIS(非嚴格的)
```cpp=
#include<bits/stdc++.h>
using namespace std ;
typedef pair<int, int> Pii ;
#define FF first
#define SS second
Pii p[10000001] ;
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0) ;
int n ;
cin >> n ;
for (int i=0;i<n;i++)
cin >> p[i].FF >> p[i].SS ;
sort(p, p+n) ; // 這樣 x 就可以照順序排
vector<int> LIS ; // 只存放 y 因為 x 已經排好了
for (int i=0;i<n;i++) {
auto idx = upper_bound(LIS.begin(), LIS.end(), p[i].SS) ;
if (idx == LIS.end()) LIS.push_back(p[i].second) ;
else *idx = p[i].SS ;
}
cout << LIS.size() << '\n' ;
return 0 ;
}
```
## LCS-最長公共子序列
所謂最長公共子序列，就是在兩個序列中各自選出一個子序列，保證這兩個子序列相同
此時的子序列長度就是 LCS 的長度，注意子序列的定義是
在序列中可以刪除某些元素但不能"調換元素順序"的產物
比如在序列 "ABCD" 中可以找到子序列 "ACD" 但沒有 "ADC"
(以下 n 代表序列一的長度，m 代表序列二的長度)
因為可以刪除與不能調換的原因，一個序列的子序列可能有 $2^n$ 個
也就是說，暴力解會達到 $O(2^{nm})$ 的時間複雜度
但如果這題用 DP 去解，時間複雜度只會是 $O(nm)$
通常我們在處理這個問題時會這樣定義
`LCS[i][j]` 位置為序列 A 的前 $i$ 個元素與序列 B 的前 $j$ 個元素的 LCS 長度
注意這裡不需要以 `A[i]` 跟 `B[j]` 作為結尾，而是表示一種終點的感覺
而在這樣的情況下，LCS 大致上有三種可能
1. 前 $i-1$ 個元素與前 $j$ 個元素
2. 前 $i$ 個元素與前 $j-1$ 個元素
4. 前 $i-1$ 個元素且前 $j-1$ 個元素 + 1
第三種情況必須在 `A[i] == B[j]` 才能做為可能
因為這裡等於是新增元素到舊的 LCS 了，必須要符合"兩者相同"的特質
```cpp=
void LCS() {
for (int i=1;i<=n;i++) {
for (int j=1;j<=m;j++) {
LCS[i][j] = max(LCS[i-1][j], LCS[i][j-1]) ;
if (A[i] == B[j]) max(LCS[i][j], LCS[i-1][j-1]+1) ;
}
}
}
```
如果細心一點就會發現，判斷 LCS 時只需要 $i-1$ 或是 $j-1$ 的位置
那這時候是不是就能使用滾動陣列呢 如果用滾動陣列就可以減少大量空間
```cpp=
void LCS() {
int f = 0, t = 1 ;
for (int i=0;i<m;i++) {
for (int j=1;j<=n;j++) {
LCS[t][j] = (s2[i] == s1[j-1]) ? LCS[f][j-1]+1 : \
max(LCS[t][j-1], LCS[f][j]) ;
}
swap(f, t) ;
}
cout << LCS[f][n] ;
}
```
### a133. 10066 - The Twin Towers
[題目連結](https://zerojudge.tw/ShowProblem?problemid=a133)
給定 $2n$ 個字串，請兩兩一組找出他們的 LCS
```cpp=
```
## 最短修改距離
給定兩個字串 $s1$, $s2$，問 $s1$ 最少要經過幾次操作才能變成 $s2$
操作可以是 "修改 $s1$ 的字元"，"去除 $s1$ 的字元"，"增加字元到 $s1$"
可以先根據比較小的情況做判斷，並定義轉移式
* 如果 $s1$ = ""(空字串)， $s1$ 變 $s2 \rightarrow s2$ 的長度
* 對於 $s2[:j]$ 來說， $s1$ 變 $s2[:j] \rightarrow j$
* 反之如果 $s2$ = ""， $s1$ 變 $s2\rightarrow s1$ 的長度
* 對於 $s1[:j]$ 來說， $s1[:j]$ 變 $s2 \rightarrow j$
* 定義轉移式 $dp[i][j] =$ $s1[:i]$ 變 $s2[:j]$
這時候就要注意了，假設 $s1[i] = s2[j]$，因為不需要更動所以會是 $dp[i-1][j-1]$
但是如果 $s1[i] \not = s2[j]$，那就會是 $min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1$
### f507. 1207 - AGTC
[題目連結](https://zerojudge.tw/ShowProblem?problemid=f507)
同樣的概念，就不再次講解了
```cpp=
#include<bits/stdc++.h>
using namespace std ;
int dp[1040][1040] ;
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0) ;
int n, m ;
string s1, s2 ;
while (cin >> n >> s1 >> m >> s2) {
for (int i=0;i<=n;i++) {
for (int j=0;j<=m;j++) {
if (i == 0) dp[0][j] = j ;
else if (j == 0) dp[i][0] = i ;
else if (s1[i-1] == s2[j-1])
dp[i][j] = dp[i-1][j-1] ;
else
dp[i][j] = min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]}) + 1 ;
}
}
cout << dp[n][m] << '\n' ;
}
return 0 ;
}
```
## 找一維區間內元素相加最大
對一串數字來說，如果我想在這串數字中找到一個區間 $T$，使這個區間 $T$ 的總和是所有 $T$ 中最大的
所以先簡單做一個移轉式 `dp[i] = 區間 T 最尾端最多到第 i 個元素的最大總和`
這個移轉式沒辦法很輕鬆的用 $O(n)$ 處理，因為你要去枚舉區間 $[\ k,j\ ]$ 的總和，$k
\le j\le i$
但是這裡可以發現兩件事情，所以能把移轉式修改成能用 $O(n)$ 的方法處理
1. 區間 $[\ k,j\ ]$ 的總和為 $[\ k,j-1\ ] + A[\ j\ ]$
2. `dp[i] = max(枚舉所有以 j 結尾的區間中的最大總和)` ，$j\le i$
這裡在對第二點做更詳細的講解，假設數字為 $\{-2,-1,1\}$
區間總共會有 $\{-2\}$、$\{-1\}$、$\{1\}$、$\{-2,-1\}$、$\{-1,1\}$、$\{-2,-1,1\}$ 六個
那假設要找 `dp[1]`，也就是最多只能跑到 $-1$，我能用的區間就是 $\{-2\}$、$\{-1\}$、$\{-2,-1\}$
所以 `dp[1] = max(-2,-1,(-2)+(-1))`，分別為這三個區間的總和，如果再進一步推導
要找 `dp[2]`，能用的區間除了之前的三個還有 $\{1\}$、$\{-1,1\}$、$\{-2,-1,1\}$
很明顯 $\{-1,1\}$、$\{-2,-1,1\}$ 是由 `dp[1]` 能用的區間加入 `A[2]`
$\{-2\}$ 不能加入 `A[2]`，因為區間必須連續，所以這裡要做一個轉換
如果 `dp2[i] = 以第 i 個元素作結尾的區間最大總和`，這樣就可以讓 `dp` 跟 `dp2` 有關聯
也就是 `dp[i] = max(dp2[0], dp2[1], ..., dp2[i])`
這時候你可能會發現一件事情，只需要求出所有的 dp2 就行，然後開始找 dp2 的規律
* 如果 `dp2[i-1] <= 0` 代表前面的區間和對找最大總和"無"幫助，所以 `dp2[i] = A[i]`
* 如果 `dp2[i-1] > 0` 代表前面的區間和對找最大總和"有"幫助，所以 `dp2[i] = dp2[i-1] + A[i]`
這時候要求一串數字的區間最大總和就可以用下列的程式碼計算
```cpp=
vector<int> A(n), dp(n, 0) ; // 長度 n
dp[0] = A[0] ;
int ans = A[0] ;
for (int i=1;i<n;i++) {
dp[i] = max(dp[i-1], 0) + A[i] ;
ans = max(ans, dp[i]) ;
}
cout << ans << '\n' ;
```
如果你搞不清楚我前面的推導的話，可以選擇將結論背起來，或是把一開始定義的移轉式拿來用
### 2191 . D. 質感測試
[題目連結](https://tioj.ck.tp.edu.tw/problems/2191)
給一個圓盤上面有多個點(預設關閉)，現在有一根棒子以圓心旋轉，長度剛好為直徑
當棒子通過某個點會將其點開啟或關閉，(如原先開啟則關閉，反之原先關閉就開啟)
每個點都會有質感係數 $x$，當點開啟時質感係數為 $x$，當關閉時質感係數為 $0$
你可以自行決定棒子一開始要放在哪裡，以及棒子旋轉角度(可以轉不到一圈)
整體質感 = 所有開啟的點質感係數總和，問最大的整體質感為多少
解題思路 :
首先要注意一個問題，因為棒子長度是直徑，所以有可能一次改到多個點
這些點有一個特性，如果你把圓心當作原點，那同斜率的點會一起被改到
所以如果用斜率做順序(注意若 $x = 0$ 需特別處理)，整個問題就會變區間最大和
但是最大總和區間有可能貫穿結尾跟起點，所以要區分情況
* 如果有貫穿 -> 總和 - 最小連續和
* 如果無貫穿 -> 最大連續和
```cpp=
#include<bits/stdc++.h>
using namespace std ;
#define SS second
// 因為可能有多個點同時被掃到(到原點斜率相同)
// 所以用 map 存同斜率的值
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0) ;
int n ;
cin >> n ;
double x, y, w ;
map<double, int> mp ;
for (int i=0;i<n;i++) {
cin >> x >> y >> w ;
if (x == 0) mp[INT_MAX] += w ; // 斜率無限大
else mp[y/x] += w ;
}
// nmax 以目前位置為結尾最大總和
// good 所有區間中最大總和
// nmin 以目前位置為結尾最小總和
// bad 所有區間中最小總和
// sum 所有元素總和
int good = 0, nmax = 0, bad = 0, nmin = 0, sum = 0 ;
for (auto& it: mp) {
nmax = max(nmax, 0) + it.SS ;
good = max(good, nmax) ;
nmin = min(nmin, 0) + it.SS ;
bad = min(bad, nmin) ;
sum += it.SS ;
}
// 答案會是區間最大或全部-區間最小
// 全部-區間最小其實是跨越區間終點跟起點的區間和
// 因為時鐘是圓形，所以起點可以為任何可能
// 而起點轉一圈到起點才是全部區間
// 所以有些區間會需要跨越區間終點
cout << max(good, sum-bad) << '\n' ;
return 0 ;
}
```
## 找一維區間內元素相乘最大
簡單來說，這題想要找的是最大乘積的子陣列
```python=
num = [-1,2,3,-4]
ans = 6 # [2,3]
num = [-1,0,-2]
ans = 0 # [0]
```
解題思路 :
有三個重點
1. 陣列裡面有負數，要考慮當下最小乘積
2. 用 dpmax, dpmin 來儲存當下最大(小)乘積
3. 最後用 ans 儲存所有最大乘積(答案)
通常我們最直覺的思考可能用列舉的方式解決，只要用兩個for迴圈就可以解決
程式碼如下 :
```python=
def find_max(nums) :
longs = len(nums)
ans = nums[0] # 最大子陣列乘積
for i in range(longs) :
now = 1
for j in range(i,longs) :
now *= nums[j] # 目前的子陣列乘積
ans = max(ans, now) # 比較
return ans
nums = [1,0,-100,101,5,0] # 505
ans = find_max(nums)
print(ans)
```
但是用這個演算法太慢了O(n^2^)
所以我們要換一個想法去執行，在這邊我們介紹DP的解法
假如我們可以用**兩個變數**去儲存**當前位置的最大(小)乘積**
這樣跑完整個陣列後就會得到全部最大(小)乘積
假設我們要找最大子陣列乘積的陣列是 [ -1 , 1 , -1 , -1 , 2 , 2 , -1 , -5 , 0 ]
可以先把情況定義好，假設我們遇到一個新的數，目前位置的最大乘積有三種可能
1. 目前位置的數值
2. 之前最大乘積
3. 之前最大乘積 × 目前位置的數值
| | 1 | 2 | 5 | 8(最後) |
| ---------------- | ---------- | ---------- | ---------- | ---------- |
| 目前位置的數值 A | 1 | -1 | 2 | 0 |
| 之前最大乘積 ans | 1 | 1 | 2 | 20 |
| A × ans | 1 | -1 | 4 | 0 |
| 結果 | 第一種 | 第二種 | 第三種 | 第二種 |
所以只要每次都判斷三種可能的大小，就能知道答案
但是還有一種可能我故意沒寫出來，記得之前我說要**考慮最小乘積**嗎
假設最小乘積是 -N ，結果 N 超大，**剛好後面接一個 -1**
之前最小乘積會**直接變成目前最大乘積**
所以還要考慮到第四種可能 **"之前最小乘積 × 目前位置的數值"** 才可以
程式碼如下 :
```python=
def find_max(nums) :
ans = nums[0] # 之前最大乘積
longs = len(nums)
dpmin = ans # 當前位置最小乘積
for i in range(1,longs) :
now = nums[i] # 當前位置的數值
max_now = now * ans # 之前最大值 × 現在的數值
min_now = now * dpmin # 之前最小值 × 現在的數值
# 判斷四種情況
ans = max(now, ans, max_now, min_now)
# 更新目前最小乘積
dpmin = min(now, max_now, min_now)
return ans
nums = [1,0,-100,101,5,0] # 505
ans = find_max(nums)
print(ans)
```
## 其他例題
### a697. [NOIP 2012 普及組] 3.摆花
解題思路 :
```cpp=
#include<bits/stdc++.h>
using namespace std ;
int dp[105] = {0} ;
signed main() {
ios::sync_with_stdio(0), cout.tie(0), cin.tie(0) ;
int n, m, i, j, k, a ;
cin >> n >> m ;
dp[0] = 1 ;
for(i=0;i<n;i++) {
cin >> a ;
for (j=m;j>=0;j--) { // 對於第 j 盆來說，還可以放入 m-j盆植物
for (k=1;k<=a;k++) {
if (j+k <= m) {
dp[j+k] = (dp[j+k] + dp[j]) % 1000007 ;
}
else break ;
}
}
}
cout << dp[m] << '\n' ;
return 0 ;
}
```
### TIOJ 2182 . 幸運表格 (Lucky)
解題思路 :
這題比較有意思，因為可以從任一點往右或下走，直到走到範圍外
可能很多人沒想到，這種問題其實是要"反過來"看的
如果要求走到範圍外，反過來就是從範圍外往左或上走求最大值
這樣我們的起點就固定為最右方與最下方的範圍外
我們拿上圖舉例，假設綠色數字為表格範圍內的數字，黑色數字在範圍外
兩個藍色箭頭指向的數字 "4"，對於這個 "4" 來說
要走到他這點有可能是從下方或右方來，之後做 max() 運算就可以了
```cpp=
#include<bits/stdc++.h>
using namespace std ;
int G[1002][1002], dp[1002][1002] ; // 範圍外預設為 0
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0) ;
int m, n ;
cin >> m >> n ;
for (int i=0;i<m;i++)
for (int j=0;j<n;j++)
cin >> G[i][j] ;
int ans = INT_MIN ;
for (int i=m-1;i>=0;i--) {
for (int j=n-1;j>=0;j--) {
dp[i][j] = max(dp[i+1][j], dp[i][j+1]) + G[i][j] ;
ans = max(ans, dp[i][j]) ;
}
}
cout << ans << '\n' ;
return 0 ;
}
```
### d784. 一、連續元素的和
解題思路 :
求最大區間和
```cpp=
#include<bits/stdc++.h>
using namespace std ;
signed main() {
ios::sync_with_stdio(0), cout.tie(0), cin.tie(0) ;
int t ;
cin >> t ;
while (t--) {
int n, i, tmp, ans, in ;
cin >> n >> ans ;
tmp = ans ;
for (i=1;i<n;i++) {
cin >> in ;
if (tmp < 0) tmp = 0 ;
tmp += in ;
ans = max(ans, tmp) ;
}
cout << ans << '\n' ;
}
return 0 ;
}
```
### APCS考古題 m373. 4. 投資遊戲
解題思路 :
先從 $k = 0$ 的情況開始判斷
定義移轉式 $dp[i]\ =$ 結尾必定 index 為 $i$ 的最大區間和(一定要放入一個數字)
從移轉式定義知道 $dp[0] = max(val[0], 0)$，那麼剩下的數字就可以被推出來
如果遇到一個新的數字 $x$，新的最大區間和有兩種可能
1. 單一個數字 $x$，可以表示成 $0+x$
2. 舊的區間和 $+x$
因為舊的區間和可能是負數，加上負數後區間和也不會比較大，還不如用 $0+val[i]$
於是 $dp[i]$ 就可以用下面的程式碼表示
`dp[i] = max(dp[i-1]+val[i], dp[i-1])`
=> `dp[i] = max(dp[i-1], 0) + val[i]`
再來判斷 $k > 0$ 的情況
因為多了一項 $k$，移轉式也要做出改變，根據最大區間和的可能情況修改
```cpp=
#include<bits/stdc++.h>
using namespace std ;
int val[150005] ;
int dp[2][22] ;
signed main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0) ;
int n, k, i, j ;
while (cin >> n >> k) {
for (i=0;i<n;i++) cin >> val[i] ;
int ans = 0 ;
dp[1][0] = 0, dp[0][0] = 0 ;
for (i=0;i<n;i++) {
int x = i%2, y = (i+1)%2 ;
dp[x][0] = max(dp[y][0],0) + val[i] ;
for(j=1;j<=k;j++)
dp[x][j] = max(dp[y][j-1], dp[y][j]+val[i]) ;
ans = max(ans, dp[x][k]) ;
}
cout << ans << '\n' ;
}
return 0 ;
}
```
```python=
n, k = 9, 0
val = [3, 1, -2, 3, -2, 3, -5, 2, 2]
dp = [[0]*(n+1) for i in range(2)]
ans = 0
for i in range(0,n) :
x = i%2
y = (i+1)%2
dp[x][0] = max(dp[y][0],0) + val[i]
for j in range(1,k+1) :
dp[x][j] = max(dp[y][j-1], dp[y][j]+val[i])
ans = max(ans, dp[x][k])
print(ans)
```
### e791. a2.空間切割(Cut)
解題思路 :
由於空間的切割可以看成是
```cpp=
#include<bits/stdc++.h>
using namespace std ;
typedef long long LL ;
LL ans[51][51] = {} ;
signed main() {
ios::sync_with_stdio(0), cout.tie(0), cin.tie(0) ;
int n, i, j, d, c ;
for (i=0;i<51;i++) {
ans[i][0] = 1 ;
ans[0][i] = 1 ;
}
for (i=1;i<51;i++)
for (j=1;j<51;j++)
ans[i][j] = ans[i][j-1] + ans[i-1][j-1] ;
cin >> n ;
while (n--) {
cin >> d >> c ;
cout << ans[d][c] << '\n' ;
}
return 0 ;
}
```
Sign in with Wallet
Connect another wallet