---
# System prepended metadata

title: 【6-8】DP

---

# 【6-8】DP

動態規劃（Dynamic Programming，簡稱 DP）聽起來像「邊走邊看」很隨興的一種演算法，但其實是一種非常有系統性作法：**找出問題中的重複子問題（overlapping subproblems）與最優子結構（optimal substructure），把子問題的解保存起來，避免重複計算。** 換句話說，DP 常常是「以空間換取時間」的策略。

題目：給定一個正整數 $k，計算 $2^k$，從 $1$ 到 $k$ 的所有結果

### 解法 A：每次都從頭乘
```cpp
for (int i = 1; i <= N; ++i) {
    long long n = 1;
    for (int j = i; j > 0; --j) n = n * 2;
    cout << "2^" << i << " = " << n << '\n';
}
```

* **時間複雜度**：$O(n^2)$
* **空間複雜度**：$O(1)$

### 解法 B：用前一個計算結果乘

```cpp
vector<long long> a(N+1);
a[0] = 1;
for (int i = 1; i <= N; ++i) {
    a[i] = a[i-1] * 2;
    cout << "2^" << i << " = " << a[i] << '\n';
}
```

* **時間複雜度**：$O(n)$
* **空間複雜度**：$O(n)$

解法 B 就是使用了 DP 的技巧，而在使用 DP 時，通常有三個要素：
* **狀態定義**：定義陣列中紀錄的內容代表什麼
* **Base case**：給出最小子問題的解
```cpp
a[0] = 1
```
* **狀態轉移**：定義如何由較小子問題組出較大問題的解
```cpp
a[i] = a[i-1] * 2
```

實作上，又有兩種常見方法，接下來的例題會盡量提供兩種解法給各位讀者參考：

* **Top-down + memoization**：遞迴求解，遇到新子問題就計算並存結果。
* **Bottom-up / tabulation**：從最小子問題開始按順序填表，直到得到答案。

---

## 0/1 背包（0/1 knapsack）

**問題**：有 `n` 件物品，第 `i` 件重量 `w[i]`、價值 `v[i]`，背包容量 `W`。每件物品最多選 1 次，不可分割，求最大總價值。

初次遇到這種問題，我們先土法煉鋼一下，假設題目如下：

背包容量W=8

|編號|重量|價值|
|-|-|-|
|1|2|1|
|2|3|2|
|3|4|5|
|4|5|6|

如果使用窮舉法，可以找到以下可能：
```
1+2+3+4：重量14 價值14 （超重）
1+2+3  ：重量9  價值8  （超重）
1+2+4  ：重量10 價值9  （超重）
1+3+4  ：重量11 價值12 （超重）
2+3+4  ：重量12 價值13 （超重）
1+2    ：重量5  價值3
1+3    ：重量6  價值6
1+4    ：重量7  價值7
2+3    ：重量7  價值7
2+4    ：重量8  價值8
3+4    ：重量9  價值11 （超重）
1      ：重量2  價值1
2      ：重量3  價值2
3      ：重量4  價值5
4      ：重量5  價值6
```
答案為 8，但窮舉法的時間複雜度是 $O(2^n)$，當物品種類變多，效率會變很差。


---

窮舉法之所以不方便解決這個問題，是因為物品過多，導致組合數太多。

既然如此，為何我們不考慮先討論兩個物品就好呢？找出兩個問題的解後，再放入第三個物品，一次增加一種，並且加入一個價值、重量皆為 0 的物品，方便討論。

### 狀態定義
`dp[i][j]`：考慮前 `i` 件物品，且背包容量為 `j` 時能達到的最大價值
### Base case
`dp[0][j] = 0`（未考慮任何物品，價值為 0）
`dp[i][0] = 0`（容量為 0，價值為 0）
### 狀態轉移
考慮第 i 種物品，最大重量為 j 的背包，比較【放 / 不放】：
* 【不放】不考慮此物品時最佳解（`dp[i-1][j]`）
* 【放】不考慮此物品且放得下此物品的最佳解 + 本物品價值（`dp[i-1][j-w[ｉ]]+v[i]`）

得到狀態轉移方程式：
```cpp
dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[ｉ]]+v[i])
```

在遍歷時要注意，ｊ必須大於等於 v[ｉ]，否則會越界（跑到陣列外）。若ｊ小於 v[ｉ]，由於無法將物品放入背包，故最佳解必為【不放】。

---

### 圖解程式

※ 紅色那格為 dp[0][0]

| 標號 | 價值 | 重量 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| 0 | 0 | 0 | <font color="#f00">**0**</font> | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 1 | 2 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 2 | 2 | 3 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 3 | 5 | 4 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 4 | 6 | 5 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

我們先對編號 1 的物體進行討論。由於ｊ必須大於等於 v[ｉ]，所以從重量上限 2 開始討論。考慮【放 / 不放】：
* 【不放】dp[0][2] = <font color="#F7A004">**0**</font>
* 【放】dp[0][2 – w[1]] + v[1] = dp[0][2 - 2] + v[1] = <font color="#00A600">**0**</font> + <font color="#0080FF">**1**</font> = <font color="#f00">**1**</font>

顯然 <font color="#f00">**1**</font> > <font color="#F7A004">**0**</font>，所以dp[1][2]= <font color="#f00">**1**</font>

| 標號 | 價值 | 重量 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| 0 | 0 | 0 | <font color="#00A600">**0**</font> | 0 | <font color="#F7A004">**0**</font> | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | <font color="#0080FF">**1**</font> | 2 | 0 | 0 | <font color="#f00">**1**</font> | 0 | 0 | 0 | 0 | 0 | 0 |
| 2 | 2 | 3 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 3 | 5 | 4 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 4 | 6 | 5 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

顯然對於重量上限 3~8 最佳解都會是 1。

| 標號 | 價值 | 重量 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 1 | 2 | 0 | 0 | 1 | <font color="#f00">**1**</font> | <font color="#f00">**1**</font> | <font color="#f00">**1**</font> | <font color="#f00">**1**</font> | <font color="#f00">**1**</font> | <font color="#f00">**1**</font> |
| 2 | 2 | 3 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 3 | 5 | 4 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 4 | 6 | 5 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

接著加入編號 2 的物體進行討論。由於ｊ必須大於等於 v[ｉ]，所以最佳解必為【不放】。

| 標號 | 價值 | 重量 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 1 | 2 | <font color="#F7A004">**0**</font> | <font color="#F7A004">**0**</font> | <font color="#F7A004">**1**</font> | 1 | 1 | 1 | 1 | 1 | 1 |
| 2 | 2 | 3 | <font color="#f00">**0**</font> | <font color="#f00">**0**</font> | <font color="#f00">**1**</font> | 0 | 0 | 0 | 0 | 0 | 0 |
| 3 | 5 | 4 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 4 | 6 | 5 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

重量上限 3 時，考慮【放 / 不放】：
* 【不放】dp[1][3] = <font color="#F7A004">**1**</font>
* 【放】dp[1][3 – w[2] + v[2] = dp[1][3 - 3] + v[2] = <font color="#00A600">**0**</font> + <font color="#0080FF">**2**</font> = <font color="#f00">**2**</font>

顯然 <font color="#f00">**2**</font> > <font color="#F7A004">**1**</font>，所以dp[1][2]= <font color="#f00">**2**</font>

| 標號 | 價值 | 重量 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 1 | 2 | <font color="#00A600">**0**</font> | 0 | 1 | <font color="#F7A004">**1**</font> | 1 | 1 | 1 | 1 | 1 |
| 2 | <font color="#0080FF">**2**</font> | 3 | 0 | 0 | 1 | <font color="#f00">**2**</font> | 0 | 0 | 0 | 0 | 0 |
| 3 | 5 | 4 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 4 | 6 | 5 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

接著重量上限 5 的時候，考慮【放 / 不放】：
* 【不放】dp[1][5] = <font color="#F7A004">**1**</font>
* 【放】dp[1][5 – w[2] + v[2] = dp[1][5 - 3] + v[2] = <font color="#00A600">**1**</font> + <font color="#0080FF">**2**</font> = <font color="#f00">**3**</font>

顯然 <font color="#f00">**3**</font> > <font color="#F7A004">**1**</font>，所以dp[1][2]= <font color="#f00">**3**</font>

| 標號 | 價值 | 重量 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 1 | 2 | 0 | 0 | <font color="#00A600">**1**</font> | 1 | 1 | <font color="#F7A004">**1**</font> | 1 | 1 | 1 |
| 2 | <font color="#0080FF">**2**</font> | 3 | 0 | 0 | 1 | 2 | 2 | <font color="#f00">**3**</font> | 0 | 0 | 0 |
| 3 | 5 | 4 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 4 | 6 | 5 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |

依此類推，完成表格，最後我們可以看到，背包重量上限 8 的情況下，考慮所有物品放入情況，最大價值為 <font color="#f00">**8**</font> 。

| 標號 | 價值 | 重量 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 1 | 2 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 2 | 2 | 3 | 0 | 0 | 1 | 2 | 2 | 3 | 3 | 3 | 3 |
| 3 | 5 | 4 | 0 | 0 | 1 | 2 | 5 | 5 | 6 | 7 | 7 |
| 4 | 6 | 5 | 0 | 0 | 1 | 2 | 5 | 6 | 6 | 7 | <font color="#f00">**8**</font> |

---

### C++範例
```cpp=
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, W;
    cin >> n >> W;
    vector<int> w(n+1), v(n+1);
    for (int i = 1; i <= n; i++) cin >> w[i] >> v[i];

    vector<vector<int>> dp(n+1, vector<int>(W+1, 0));

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= W; j++) {
            dp[i][j] = dp[i-1][j];
            if (j >= w[i])
                dp[i][j] = max(dp[i][j], dp[i-1][j - w[i]] + v[i]);
        }
    }

    cout << dp[n][W];
}

```

## LCS（Longest Common Subsequence）
**問題**：LCS（最長共同子序列）的定義為出現於每一個序列、而且是最長的子序列，給定兩字串 `s1`、`s2`，試求 `s1` 和 `s2` 的 LCS 長度與 LCS 為何？

我們先看個例子確保了解 LCS 的概念：
```
longest
love
```
從頭開始比較，`l` 相同，`o` 相同，下一個是 `e`，因此兩者的 LCS 為 `loe`

再看一個例子：
```
abcdefghijklmnzyxwvutsrqpo
opqrstuvwxyzabcdefghijklmn
```
這時候就頭昏眼花了吧，有沒有什麼方法可以讓我們有系統性的找出最長共同子序列呢？

---

回到最一開始的舉例，我們來從中觀察看看有沒有可以轉化成 DP 的可能性：
```
longest
love
```
既然第一個字母 `l` 相同，那我其實只需要找到 `ongest` 和 `ove` 的最長共同子序列，再補上 `l` 就是答案了。
```
ongest
ove
```
既然第一個字母 `o` 相同，那我其實只需要找到 `ngest` 和 `ve` 的最長共同子序列，再補上 `o` 就是答案了。
```
ngest
ve
```
`v` 和 `ngest` 都沒有相同的字母，這時候要把 `e` 還是 `v` 刪掉，好像都不對，兩種情況都應該考慮才對，但總之，LCS 的長度並沒有改變。

---

不過要是呼叫遞迴，複雜度就會變成 $O(2^n)$ (討論兩種情況)，顯然不是我們樂見的，怎麼辦呢？

其實剛才處理的過程，我們觀察到一個很有用的東西：
* 相同：LCS 長度 +1，可以移除該相同字元
* 不同：不影響 LCS 長度

那我們不妨用雙重 `for` 來找出兩字串相同的字元，並在找到以後記錄下來 LCS 長度

### 狀態定義

`dp[i][j]`：字串 `s1` 的前 `i` 個字元與字串 `s2` 的前 `j` 個字元的 LCS 長度。

### Base case

`dp[0][j] = 0`（未考慮任何字元，LCS 必為空字串，長度為 0）
`dp[i][0] = 0`（未考慮任何字元，LCS 必為空字串，長度為 0）

### 狀態轉移
```cpp
if(s1[i] == s2[j]){
    dp[i][j] = dp[i-1][j-1] + 1;
}
else{
    dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
}
```


---

### 圖解程式

|  |  | l | o | n | g | e | s | t |
| --- | --- | --- | --- | --- | --- | --- | --- | --- |
|   | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| **l** | 0 |  |  |  |  |  |  |  |
| **o** | 0 |  |  |  |  |  |  |  |
| **v** | 0 |  |  |  |  |  |  |  |
| **e** | 0 |  |  |  |  |  |  |  |

從左上開始，先比較 l 和 l 是否相同，發現相同，所以從左上那格+1填入此格。

|  |  | <font color="#f00">l</font> | o | n | g | e | s | t |
| --- | --- | --- | --- | --- | --- | --- | --- | --- |
|   | <font color="#1936C9">**0**</font> | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| <font color="#f00">**l**</font> | 0 | <font color="#AC19C9">**1**</font> |  |  |  |  |  |  |
| **o** | 0 |  |  |  |  |  |  |  |
| **v** | 0 |  |  |  |  |  |  |  |
| **e** | 0 |  |  |  |  |  |  |  |

接著比較 o 和 l 是否相同，發現不同，所以從上方和左方挑選最大的填入此格。

|  |  | l | <font color="#f00">o</font> | n | g | e | s | t |
| --- | --- | --- | --- | --- | --- | --- | --- | --- |
|   | 0 | 0 | <font color="#1936C9">**0**</font> | 0 | 0 | 0 | 0 | 0 |
| <font color="#f00">**l**</font> | 0 | <font color="#1936C9">**1**</font> | <font color="#AC19C9">**1**</font> |  |  |  |  |  |
| **o** | 0 |  |  |  |  |  |  |  |
| **v** | 0 |  |  |  |  |  |  |  |
| **e** | 0 |  |  |  |  |  |  |  |

依序遍歷完後，會得到下方表格：

|  |  | l | o | n | g | e | s | t |
| --- | --- | --- | --- | --- | --- | --- | --- | --- |
|   | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| **l** | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| **o** | 0 | 1 | 2 | 2 | 2 | 2 | 2 | 2 |
| **v** | 0 | 1 | 2 | 2 | 2 | 2 | 2 | 2 |
| **e** | 0 | 1 | 2 | 2 | 2 | 3 | 3 | 3 |

LCS 長度為 3

可以用這個 [LCS建表練習](https://alchemist-al.com/algorithms/longest-common-subsequence) 檢測看看自己有沒有理解喔！

---

此時若題目只詢問 LCS 長度，就只需要輸出最後一格就好了，但想知道這個 LCS 具體是什麼也難不倒我們，只需要把剛才遍歷的狀態轉移倒轉就可以了：

* 優先往大的地方走（只能往左和往上）
* 發現下一格數字改變，記錄字母於陣列中，並且跳到左上方的格子

|  |  | l | o | n | g | <font color="#f00">e</font> | s | t |
| --- | --- | --- | --- | --- | --- | --- | --- | --- |
|   | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| **l** | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| **o** | 0 | 1 | 2 | 2 | 2 | 2 | 2 | 2 |
| **v** | 0 | 1 | 2 | 2 | <font color="#F7A004">2</font> | 2 | 2 | 2 |
| <font color="#f00">**e**</font> | 0 | 1 | 2 | 2 | <font color="#1936C9">**2**</font> | <font color="#AC19C9">**3**</font> | 3 | 3 |

陣列：`e`

優先往大的地方走（但是只能往左和往上）。

|  |  | l | o | n | g | e | s | t |
| --- | --- | --- | --- | --- | --- | --- | --- | --- |
|   | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| **l** | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| **o** | 0 | 1 | <font color="#F7A004">2</font> | 2 | 2 | 2 | 2 | 2 |
| **v** | 0 | 1 | <font color="#AC19C9">**2**</font> | 2 | 2 | 2 | 2 | 2 |
| **e** | 0 | 1 | 2 | 2 | 2 | 3 | 3 | 3 |

|  |  | l | <font color="#f00">o</font> | n | g | e | s | t |
| --- | --- | --- | --- | --- | --- | --- | --- | --- |
|   | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| **l** | 0 | <font color="#F7A004">1</font> | 1 | 1 | 1 | 1 | 1 | 1 |
| <font color="#f00">**o**</font> | 0 | <font color="#1936C9">**1**</font> | <font color="#AC19C9">**2**</font> | 2 | 2 | 2 | 2 | 2 |
| **v** | 0 | 1 | 2 | 2 | 2 | 2 | 2 | 2 |
| **e** | 0 | 1 | 2 | 2 | 2 | 3 | 3 | 3 |

陣列：`e,o`

|  |  | <font color="#f00">l</font> | o | n | g | e | s | t |
| --- | --- | --- | --- | --- | --- | --- | --- | --- |
|   | <font color="#F7A004">0</font> | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| <font color="#f00">**l**</font> | <font color="#1936C9">**0**</font> | <font color="#AC19C9">**1**</font> | 1 | 1 | 1 | 1 | 1 | 1 |
| **o** | 0 | 1 | 2 | 2 | 2 | 2 | 2 | 2 |
| **v** | 0 | 1 | 2 | 2 | 2 | 2 | 2 | 2 |
| **e** | 0 | 1 | 2 | 2 | 2 | 3 | 3 | 3 |

陣列：`e,o,l`
最後反向輸出陣列即可得到最長共同子序列 `loe` 。

---

### C++範例
```cpp=
#include <bits/stdc++.h>
using namespace std;

int main() {
    string A, B;
    cin >> A >> B;
    int n = A.size(), m = B.size();

    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));

    // 填 DP 表
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (A[i - 1] == B[j - 1])
                dp[i][j] = dp[i - 1][j - 1] + 1;
            else
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
        }
    }

    // 反向追溯 LCS 字串
    string lcs = "";
    int i = n, j = m;
    while (i > 0 && j > 0) {
        if (A[i - 1] == B[j - 1]) {
            lcs += A[i - 1];
            i--; j--;
        } else if (dp[i - 1][j] >= dp[i][j - 1]) {
            i--;
        } else {
            j--;
        }
    }

    reverse(lcs.begin(), lcs.end());

    cout << "LCS length = " << dp[n][m] << "\n";
    cout << "LCS string = " << lcs;
}

```


---

## LIS(Longest Increasing Subsequence)
**問題**：LIS（最長遞增子序列）的定義為所有子序列中，遞增的、最長的子序列。今給定一數列 `S`，試問其 LIS 長度與 LIS 序列為何？
```
1 4 2 3
```
我們可以把所有子序列找出來：
```
1 4 2 3
1 4 2
1 4 3
1 2 3
1 4
1 2
1 3
1
4 2 3
4 2
4 3
4
2 3
2
3
```
其中不屬於遞增（由小到大）的我們將其移除，留下遞增子序列：
```
1 2 3
1 4
1 2
1 3
1
2 3
2
3
```
這之中最長的為 1 2 3，故最長遞增子序列為 1 2 3，長度為3。

但窮舉出每一種可能的複雜度是 $O(2^n)$，顯然不是一個好的方法。

---

我們根據 LIS 的規則，不難發現其要求有兩點：
* 前後順序不變
* 數值遞增

那麼，有了 LCS 的經驗，我們再一次透過雙重 `for` 迴圈，但這次改比較兩個數字的大小關係，要是後者大於前者就代表可以加入 LIS 中(但不保證是最優解)，反之就不可能放入 LIS。

### 狀態定義

`dp[i]`：數列 `S` 的前 `i` 個數值的 LIS 長度。

### Base case

`dp[i] = 1`（所有數字都可以自己成為 LIS）

### 狀態轉移
```cpp
// i<j
if(S[i]<S[j]){
    dp[j]=max(dp[i]+1,dp[j]);
}
else{
    dp[j]=dp[j-1];
}
```

---

### 圖解程式

4 > 1，`max`（1 + 1 , 1）= 2。

| <font color="#1936C9">1</font> | <font color="#f00">4</font> | 2 | 3 |
|---- | ---- | ---- | ---- |
| <font color="#F7A004">**1**</font> | <font color="#AC19C9">**2**</font> | 1 | 1 |

2 > 1，`max`（1 + 1 , 1）= 2。

| <font color="#1936C9">1</font> | 4 | <font color="#f00">2</font> | 3 |
|---- | ---- | ---- | ---- |
| <font color="#F7A004">**1**</font> | 2 | <font color="#AC19C9">**2**</font> | 1 |

2 < 4，不變。

| 1 | <font color="#1936C9">4</font> | <font color="#f00">2</font> | 3 |
|---- | ---- | ---- | ---- |
| 1 | <font color="#F7A004">**2**</font> | <font color="#AC19C9">**2**</font> | 1 |

3 > 1，`max`（1 + 1 , 1）= 2。

| <font color="#1936C9">1</font> | 4 | 2 | <font color="#f00">3</font> |
|---- | ---- | ---- | ---- |
| <font color="#F7A004">**1**</font> | 2 | 2 | <font color="#AC19C9">**2**</font> |

3 < 4，不變。

| 1 | <font color="#1936C9">4</font> | 2 | <font color="#f00">3</font> |
|---- | ---- | ---- | ---- |
| 1 | <font color="#F7A004">**2**</font> | 2 | <font color="#AC19C9">**2**</font> |

3 > 2，`max`（2 + 1 , 2）= 3。

| 1 | 4 | <font color="#1936C9">2</font> | <font color="#f00">3</font> |
|---- | ---- | ---- | ---- |
| 1 | 2 | <font color="#F7A004">**2**</font> | <font color="#AC19C9">**3**</font> |

故 LIS 長度為 3

可以用這個 [LIS操作練習](https://alchemist-al.com/algorithms/longest-increasing-subsequence) 檢測看看自己有沒有理解喔！

---

若要找出此子序列，我們可以依照動態轉移的規則進行反向遍歷。

* 紀錄第一個此長度的數字
* 長度為 1 時結束

首次出現長度為 3，紀錄 3。

| 1 | 4 | 2 | <font color="#f00">3</font> |
|---- | ---- | ---- | ---- |
| 1 | 2 | 2 | <font color="#AC19C9">**3**</font> |

首次出現長度為 2，紀錄 2。

| 1 | 4 | <font color="#f00">2</font> | 3 |
|---- | ---- | ---- | ---- |
| 1 | 2 | <font color="#AC19C9">**2**</font> | 3 |

長度 2 並非首次出現，跳過不紀錄。

| 1 | <font color="#f00">4</font> | 2 | 3 |
|---- | ---- | ---- | ---- |
| 1 | <font color="#AC19C9">**2**</font> | 2 | 3 |

首次出現長度為 1，紀錄 1。

| <font color="#f00">1</font> | 4 | 2 | 3 |
|---- | ---- | ---- | ---- |
| <font color="#AC19C9">**1**</font> | 2 | 2 | 3 |

---

### C++範例
```cpp=
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    vector<int> dp(n, 1), pre(n, -1); // pre[i] 記錄 dp[i] 來源位置
    int ans = 1, pos = 0;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (a[j] < a[i] && dp[j] + 1 > dp[i]) {
                dp[i] = dp[j] + 1;
                pre[i] = j;
            }
        }
        if (dp[i] > ans) {
            ans = dp[i];
            pos = i;
        }
    }

    // 反向尋找 LIS 序列
    vector<int> lis;
    for (int i = pos; i != -1; i = pre[i])
        lis.push_back(a[i]);
    reverse(lis.begin(), lis.end());

    cout << "LIS length = " << ans << "\n";
    cout << "LIS sequence = ";
    for (int x : lis) cout << x << " ";
}

```


---

### 補充(只求LIS長度)
若是題目只求LIS長度，我們可以用偷懶一點的方式：嘗試找到 LIS 每個位置中可以擺放的最小值。(複雜度：$nlogn$)
```cpp=
#include<bits/stdc++.h>

using namespace std;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    vector<int> a(n); // 原序列
    for(int i=0;i<n;i++){
        cin >> a[i];
    }
    vector<int> b; // LIS每個位置的最小值
    for(int i=0;i<n;i++){
        if(b.empty() or b.back()<a[i]){ // 空序列or現在這個數比LIS最後一位還大
            b.push_back(a[i]); // 插入到LIS最後方
        }
        else{
            *lower_bound(b.begin(),b.end(),a[i])=a[i];
            // 使用二分搜找到第一個大於a[i]的數字，將其替換成更小的a[i]。
        }
    }
    cout << b.size(); // 輸出LIS長度
    return 0;
}

```


---

聯絡方式：codecodefunny@gmail.com
最後編修時間：2025/10/19 子柚筆