【6-8】DP - HackMD

# 【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^" < 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 | **0** | 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] = **0** * 【放】dp[0][2 – w[1]] + v[1] = dp[0][2 - 2] + v[1] = **0** + **1** = **1** 顯然 **1** > **0**，所以dp[1][2]= **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** | 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 | **1** | **1** | **1** | **1** | **1** | **1** | | 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 | **0** | **0** | **1** | 1 | 1 | 1 | 1 | 1 | 1 | | 2 | 2 | 3 | **0** | **0** | **1** | 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] = **1** * 【放】dp[1][3 – w[2] + v[2] = dp[1][3 - 3] + v[2] = **0** + **2** = **2** 顯然 **2** > **1**，所以dp[1][2]= **2** | 標號 | 價值 | 重量 | 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** | 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] = **1** * 【放】dp[1][5 – w[2] + v[2] = dp[1][5 - 3] + v[2] = **1** + **2** = **3** 顯然 **3** > **1**，所以dp[1][2]= **3** | 標號 | 價值 | 重量 | 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** | 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 的情況下，考慮所有物品放入情況，最大價值為 **8** 。 | 標號 | 價值 | 重量 | 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 | **8** | --- ### 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填入此格。 | | | l | o | n | g | e | s | t | | --- | --- | --- | --- | --- | --- | --- | --- | --- | | | **0** | 0 | 0 | 0 | 0 | 0 | 0 | 0 | | **l** | 0 | **1** | | | | | | | | **o** | 0 | | | | | | | | | **v** | 0 | | | | | | | | | **e** | 0 | | | | | | | | 接著比較 o 和 l 是否相同，發現不同，所以從上方和左方挑選最大的填入此格。 | | | l | o | n | g | e | s | t | | --- | --- | --- | --- | --- | --- | --- | --- | --- | | | 0 | 0 | **0** | 0 | 0 | 0 | 0 | 0 | | **l** | 0 | **1** | **1** | | | | | | | **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 | 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 | 陣列：`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 | 2 | 2 | 2 | 2 | 2 | 2 | | **v** | 0 | 1 | **2** | 2 | 2 | 2 | 2 | 2 | | **e** | 0 | 1 | 2 | 2 | 2 | 3 | 3 | 3 | | | | 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 | 陣列：`e,o` | | | 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 | 陣列：`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。 | 1 | 4 | 2 | 3 | |---- | ---- | ---- | ---- | | **1** | **2** | 1 | 1 | 2 > 1，`max`（1 + 1 , 1）= 2。 | 1 | 4 | 2 | 3 | |---- | ---- | ---- | ---- | | **1** | 2 | **2** | 1 | 2 < 4，不變。 | 1 | 4 | 2 | 3 | |---- | ---- | ---- | ---- | | 1 | **2** | **2** | 1 | 3 > 1，`max`（1 + 1 , 1）= 2。 | 1 | 4 | 2 | 3 | |---- | ---- | ---- | ---- | | **1** | 2 | 2 | **2** | 3 < 4，不變。 | 1 | 4 | 2 | 3 | |---- | ---- | ---- | ---- | | 1 | **2** | 2 | **2** | 3 > 2，`max`（2 + 1 , 2）= 3。 | 1 | 4 | 2 | 3 | |---- | ---- | ---- | ---- | | 1 | 2 | **2** | **3** | 故 LIS 長度為 3 可以用這個 [LIS操作練習](https://alchemist-al.com/algorithms/longest-increasing-subsequence) 檢測看看自己有沒有理解喔！ --- 若要找出此子序列，我們可以依照動態轉移的規則進行反向遍歷。 * 紀錄第一個此長度的數字 * 長度為 1 時結束首次出現長度為 3，紀錄 3。 | 1 | 4 | 2 | 3 | |---- | ---- | ---- | ---- | | 1 | 2 | 2 | **3** | 首次出現長度為 2，紀錄 2。 | 1 | 4 | 2 | 3 | |---- | ---- | ---- | ---- | | 1 | 2 | **2** | 3 | 長度 2 並非首次出現，跳過不紀錄。 | 1 | 4 | 2 | 3 | |---- | ---- | ---- | ---- | | 1 | **2** | 2 | 3 | 首次出現長度為 1，紀錄 1。 | 1 | 4 | 2 | 3 | |---- | ---- | ---- | ---- | | **1** | 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 子柚筆