<style> .reveal .slides { text-align: left; font-size:30px } </style> # Dynamic Programming ## 動態規劃 2025/12/8 ---- ### 搞懂這些 一秒變成通靈大師 - 核心概念及前言 - 認識 DP - DP 的時間複雜度&&轉移式 - DP 實作範例 - DP 優化 --- ## 前言及核心概念 ---- ### 前言 -- DP 是啥? - 動態規劃：透過解決小問題組合成大問題的答案 - DP 題通常難以被其他算法取代，且題型多種多樣 - 為什麼會說 DP 是通靈則是因為一定程度的題目通常轉移式都不好求，很吃你的直覺 - ~~遇到DP題的頻率大概為 1-2 題/場，但 **台灣站 3 題/場**，因此若是你 DP 很強可以拿去說嘴很久~~ ---- ### 核心概念 -- DP的必知知識 - 分解 : 將大問題分解成小問題，計算出小問題的答案後再合併出大問題的解 - DP(動態規劃) : 分治法的延伸。當分割出來的子問題，一而再、再而三出現，儲存這些問題的答案，避免重複求解，以**空間換取時間** - 遇到問題 $\to$ 尋找問題分割方法 $\to$ 把大問題分割成更小的問題 $\to$ 設計計算過程 $\to$ 實作 ---- ### 尋找問題分割方法 通常在 DP 裡面，總是可以找到當前狀態的前幾個狀態合併成為當前狀態，而特性如下 1. 子問題與原問題的求解方式類似 2. 子問題會一而再、再而三的出現 3. 子問題以及原問題之間存在一定關係 ---- ### 把大問題遞迴分割成更小的問題 根據以上幾點，尋找到問題之間的關係後，即可分割成小問題去進行求解，求解過程主要是對小問題進行解答後，在根據小問題的答案進行下一步操作 ---- ### 設計計算過程 1. 確認每個問題需要哪些子問題來計算答案 2. 確認總共有哪些問題 3. 把問題一一對應到表格 4. 決定問題的計算順序 5. 確認初始值、計算範圍 ---- ### 實作 分別有兩種方式 1. **top-down** : - 程式碼中採用遞迴結構計算 - 從大問題往小問題遞迴 (因此小問題先被解決) - 這個實作方式的好處為只計算必要的問題 - 以及不必煩惱計算優先順序 3. **bottom-up** : - 先理出計算順序，然後由最小的問題開始計算 - 特色是程式碼通常只有幾個迴圈 - 這個實作方式的好處為常數較低、可以自由控制計算順序 - 不必擔心 stack overflow (遞迴過多層) --- ### 通靈的路上-認識DP 先看過兩題例題，為經典的記憶化搜索 ---- ### 例題Q1. 階乘求解 給你 $q$ 次詢問 每次給定數字 $n$ 詢問 $n!$ 為多少 根據前面的步驟，會發現 $n!$ 跟 $n-1$ 的關係為 $(n-1)! \times n$ 所以就可以分割問題為 $1!,2!,3!,...,(n-1)!,n!$ 設計方法則為：每一層是前一層 $\times$ 當前層數 $[ (n-1)! \times n ]$ 實作方法則在下面做出簡單的範例 ```cpp= void factorial(){ f[0] = 0; f[1] = 1; for (int i=2; i<=N; i++) f[i] = f[i-1] * i; } ``` ---- ### Q1 的時間複雜度、空間複雜度分析 - 時間複雜度 : 總共 $N$ 個問題，每個問題花費 $O(1)$ 時間，總共花費 $O(N)$ 時間 - 空間複雜度 : 求 $1!$ 到 $N!$, 總共 $N$ 個問題， 用大小為 $N$ 的陣列儲存全部問題的答案，空間複雜度 $O(N)$ ---- ### 例題Q2 [遞迴數學式求解](https://zerojudge.tw/ShowProblem?problemid=d212)  $q$ ($1$ $\le q \le 2\times 10^5$) 筆詢問 每筆詢問給予一個數字 $n$ ($1$ $\le n \le 10^6$) ， 求 $f [ n ]$ 值為多少 ---- ### 思路 首先我們分析暴力做他的時間複雜度 發現到這樣直接暴力解 $f(n-2)+f(n-1)$ 做會 TLE 只需要開一個大小為 $10^6$ 的陣列 $dp$ 然後 $dp[i]$ 儲存 $f(i)$ 的結果就好，具體代碼如下 ---- ### top-down ```cpp int f(int n){ if (n == 0 || n == 1) return 1; // 用 0 代表該問題還未計算答案 if (table[n]) return table[n]; return table[n] = f(n-1) + f(n-2); } int main(){ f(N); int q; while(cin >> q){ cout << f(q) << '\n'; } } ``` ---- ### Bottom-up ```cpp int main(){ table[0] = 1; table[1] = 1; for (int i=2; i<=N; i++) table[i] = table[i-1] + table[i-2]; int q; while(cin >> q){ cout << table[q] << '\n'; } } ``` ---- ### Q2 的時間複雜度、空間複雜度分析 - 時間複雜度 : 總共 $N$ 個問題，每個問題花費 $O(1)$ 時間，總共花費 $O(N)$ 時間 - 空間複雜度 : 求 $1$ 到 $N$,總共 $N$ 個問題， 用大小為 $N$ 的陣列儲存全部問題的答案，空間複雜度 $O(N)$ ---- ### Top-Down v.s. Bottom-Up - 理論上兩者時間複雜度相同，但前者用遞迴實作通常常數較大 - 對於 top-down，若一開始直接呼叫很大的狀態可能會 stack overflow - bottom-up 需要找出好的計算順序，對於有些DP不易找到 - top-down 只會計算該次呼叫所需要用到的所有子狀態，而 bottom-up 一次記算完所有子狀態 - 對於狀態很疏鬆的 DP，bottom-up 可能會計算很多冗餘的狀態 ---- - 如果狀態緊密且容易找出計算順序就用 bottom-up (常數小，沒有RE風險) - 反之才用 top-down - 大多 DP 都是由小計算到大因此容易找順序，除了少數DP有很奇怪的轉移式 - 大多 DP 狀態都是滿的，通常是暴搜的記憶化搜索才會是疏鬆的狀態 --- ## DP 的時間 / 空間複雜度 && 轉移式 ---- ### DP的時間 / 空間複雜度 簡單的時間複雜度 : 狀態數 $\times$ 轉移複雜度 難的時間複雜度 : 根據每個人會有不同的實作方式去計算 狀態數 : 計算最終答案總共需要用到的子問題數量 轉移複雜度 : 計算任一個子問題的複雜度 空間複雜度 : 很直觀根據你開了多少來確定，應該不用太多描述 ---- ### DP 的轉移式 - 轉移式是用來表達 DP 的數學式子，類似遞迴數列的式子 - 不管你用何種實作方式都可以寫出一種 DP 的轉移式，有些簡單明瞭有些複雜到爆 - 主要是描述如何用小問題的解計算出大問題的解，也就是大問題跟小問題之間的關係 - greedy vs DP - greedy：使用同個策略，原問題最佳解包含子問題最佳解 - DP：用子問題的解來計算原問題的解 (複雜時會用不同策略) <!-- 與 greedy 不同的是 greedy 是一直使用同種策略，dp 在複雜時會使用小問題擇優，或是多個小問題的集合求解 --> ---- - [遞迴數學式問題](https://zerojudge.tw/ShowProblem?problemid=d212) $f(n)=f(n-1)+f(n-2)$ - [單調隊列優化](https://zerojudge.tw/ShowProblem?problemid=c528) $dp[i]=\max\limits_{0\le j\lt i,i-j<=k}\{dp[j]+a[i]\}$ - [二維背包問題](https://zerojudge.tw/ShowProblem?problemid=a587) $dp[i][j]=\max({dp[i-1][j],dp[i-1][j-w[i]]+c[i]})$ - [LIS (最長遞增子序列)](https://zerojudge.tw/ShowProblem?problemid=d052)$dp[i]=\max(dp[i],dp[j]+1),\forall arr[i] > arr[j]\land i > j$ - [LCS (最長公共子序列)](https://zerojudge.tw/ShowProblem?problemid=c001) $dp[i][j]=\begin{cases}dp[i-1][j-1]+1,s[i]=t[j]\\ \max(dp[i-1][j],dp[i][j-1]),s[i]\ne t[j]\end{cases}$ ---- ### DP 的生命就是轉移式 - 清楚且完整的表達 DP 的關係 - 每一個 DP 狀態都有他所代表的東西 - 從轉移式中可以看出遞迴計算大問題所需要的子狀態與計算方式 - 大多 DP 可以從轉移式看出總狀態數與轉移複雜度 - 列出轉移式後，照著打就可以輕鬆的寫出 DP 的程式了 (尤其是 top-down) - 容易推導 DP 優化 ---- ### 有趣的 DP 主題 - 經典 DP 問題： 背包問題、零錢問題、LCS、LIS - 在某些結構上 DP： DP on DAG、樹 DP、區間 DP、數位 DP、狀壓 DP、SOS DP - 數學、遞迴式： 排列組合、計數、機率 - DP 優化： 單調隊列優化、斜率優化、四邊形優化、分治優化、矩陣快速冪優化、aliens 優化 --- ## 下課時間 --- ### DP經典問題實戰 * 零錢問題 * 背包問題 * 最長遞增子序列(LIS) * 最長共同子序列(LCS) ---- ### 零錢問題 題序 : 身上帶太多的零錢會很麻煩，因此會希望店員在找零錢能夠以最少的硬幣數來找，而不是全部都用 1 元塞給我們 :cactus: 也就是要用最少的硬幣數湊出目標數字，具體作法為比較「每個硬幣的面額」與「其次小硬幣的面額」 :moneybag: ---- 假設需要找 \$86 【[情況1](https://zerojudge.tw/ShowProblem?problemid=d904)】硬幣有：\$50, \$10, \$5, \$1 四種面額，由於每個數字都是次小數字的倍數，因此可以直接用greedy寫掉，從最大的硬幣去選。 答案為 50\*1 + 10\*3 + 5\*1 + 1\*1 總共六枚 【[情況2](https://zerojudge.tw/ShowProblem?problemid=d133)】硬幣有：\$50, \$46, \$10, \$5, \$1 五種面額，這時會發現 greedy 好像怪怪的，因此這時候就需要使用「動態規劃」去完成這題。 ---- ### top-down 使用遞迴法，分割子問題 目標(原問題)：要算出 86 元的最少硬幣數量 有 \$50, \$46, \$10, \$5, \$1 這些種類的硬幣 分割為子問題: - 先找一個 $50，繼續求剩下的 $36 的最少硬幣數量 - 先找一個 $46，繼續求剩下的 $40 的最少硬幣數量 - 先找一個 $10，繼續求剩下的 $76 的最少硬幣數量 - 先找一個 $5，繼續求剩下的 $81 的最少硬幣數量 - 先找一個 $1，繼續求剩下的 $85 的最少硬幣數量 透過把大問題分解成更小的問題求解 ---- ```cpp vector<int> coins = {50, 46, 10, 5, 1}; int minimumChange(int x){ if(x == 0) return 0; int mn = 1e9; // 答案初始設成無限大(不可能達成) for(int i : coins){ if(x >= i){ // 判斷當前要找的錢 x 是否 >= 零錢 i // 使用一個大小為 i 的零錢找零，剩下的 $(x - i) 繼續求解 mn = min(mn, 1 + minimumChange(x - i)); } } return mn; } ``` ---- 過程中會發現同一個值 x 可能會出現很多次 以 76 為例: - $86 - 10 = 76$ - $86 - 5 - 5 = 76$ - $86 - 1 - 1 - 1 - 1 - 1 - 5 = 76$ - $86 - 1 - 1 ... - 1 = 76$ 如果每次 minimumChange(76) 都重新求解，則會花費很多時間 ---- ### 回到 DP 的核心概念 當分割出來的子問題，一而再、再而三出現，儲存這些問題的答案，避免重複求解，以空間換取時間。 - DP 狀態: $dp[ x ]$ - 紀錄目前要湊成金額 $x$ 的最少硬幣數目。 - 狀態轉移：當用一個硬幣面額 $\text{coins}[i]$ 可以使用更少的硬幣數目來湊成金額 $x$ 時，更新 $dp[x] = \min( dp[x], dp[x~– ~\text{coins}[i]] + 1)$ ---- ```cpp vector<int> coins = {50, 46, 10, 5, 1}; int dp[100]; // 開大小至少為 n 的表格，紀錄所有會出現的狀態 int minimumChange(int x){ if(x == 0) return 0; if(dp[x]) return dp[x]; // 如果已經計算過了，則直接回傳這個問題的答案 int mn = 1e9; // 答案初始設成無限大(不可能達成) for(int i : coins){ if(x >= i){ // 判斷當前要找的錢 x 是否 >= 零錢 i // 使用一個大小為 i 的零錢找零，剩下的 $(x - i) 繼續求解 mn = min(mn, 1 + minimumChange(x - i)); } } return dp[x] = mn; // 每次算完一個問題的答案，把答案儲存起來 } ``` ---- ### 時間複雜度 找錢的範圍為 $n$，零錢種類數量 $m$， $n$ 個問題，每個問題有 $m$ 個轉移 因此時間複雜度為 $O(nm)$ ### 空間複雜度 開了大小為 $n$ $(要找的錢大小)$ 的陣列，複雜度 $O(n)$ ---- ### bottom-up - $dp[ i ]$：紀錄目前要湊成金額 $x$ 的最少硬幣數目。 - 初始化 : $dp[i] = \begin{cases}0, & i = 0\\ \infty, & i > 0\end{cases}$ - 狀態轉移：當已經知道 $dp[i]$ 最少需要多少硬幣時，使用 $\text{coins}[j]$ 更新 $dp[i + \text{coins}[j]] = \min( dp[i + \text{coins}[j]], dp[ i ] + 1 )$ - 時間複雜度 : 找錢的範圍 $n$，零錢種類數量 $m$，總共有 $nm$ 個問題，因此時間複雜度為 $O(nm)$ ---- ### [0 / 1 背包問題](https://zerojudge.tw/ShowProblem?problemid=b131) $n$ 個物品 (每個物品都有重量 & 價值)。我們希望儘量將物品們塞進背包裡面，使背包裡面的物品總價值最高，but 背包有重量限制 $w$ :handbag: <!-- 這就是廣為人知的背包問題，其有許多變形，而本堂課將介紹最經典的「0/1 背包問題」 --> 「0 / 1」的意思是：每個物品只會放進背包零個或一個。一個物品要嘛整個不放進背包、要嘛整個放進背包，且物品無法切割 ---- ### 迷思 :x: 錯誤的直覺：對價值 or CP 值 (價值 $\div$ 重量) 做貪心法 <!-- 看到這種問題若沒學過直覺通常會是貪心，不管是貪心他的價值或是貪心他的 CP 值也好，在這種題目下面都是錯的 --> :o: 利用背包的剩餘重量，找出最好的物品組合方式 <!-- 0/1 背包問題的關鍵點，在於如何有效利用背包的剩餘重量，找出最好的物品組合方式 --> ---- ### 分割問題 對某一件物品，可選擇放或不放，然後移去這件物品，縮小問題範圍： - 一件物品不放進背包，背包價值不變、背包耐重不變 - 一件物品放進背包，背包價值上升、背包耐重下降 $~$ 當我們挑選第 $i$ 個物品，且重量上限為 $w$ 時，遞迴公式為： $$ c (i, w) =\max( c(i-1, w),~c(i-1, w-\text{weight}[i]) + \text{cost}[i]) $$ 有這條公式就可以設計 top-down 演算法 (但通常不會這麼做) <!-- .element: class="fragment" data-fragment-index="1" --> ---- <div style="position: absolute; left: 0%; top:100%;"> Sample input 第一行輸入 $N, w$ 接下來輸入物品 $i$ 的重量 / 價值 ``` cpp 4 5 // N w 2 3 // i = 1 1 2 // i = 2 3 4 // i = 3 2 2 // i = 4 ``` Sample output ``` 7 ``` 可以輕鬆得到右邊的圖 top-down 就是從 [4,5] 往下遞迴 </div> <div style="position: absolute; right: 0%; top:100%;">  </div> ---- ### 一些發現 - 注意到在 top-down 中許多點沒有被訪問到 (我只有把訪問到的邊畫出來) - 過程中，$dp[n][w]$ 這個狀態是可以記錄的，會不斷重複出現 - 每次遞迴相當於多一個節點 - 總共可能會有的 $N\cdot w$ 個節點 - 在實作上通常會使用 bottom-up ---- bottom-up 的迴圈版本如下: ```cpp for (int i = 1; i <= n; ++i) for (int j = weight[i]; j <= w; j++) // 由後往前 dp[i][j] = max(dp[i][j], dp[i-1][j - weight[i]] + cost[i]); ``` 非常簡潔 <!-- .element: class="fragment" data-fragment-index="1" --> ---- * $dp[ i ][ j ]$：紀錄使用前 $i$ 個元素，背包重量使用了 $j$ 的最大價值 * 測試每個物品 $\text{weight}[ i ]$ 放或不放，誰的價值總和比較高 * 狀態轉移：當有一個更好的方法是在同重量下可以獲得更高價值時，更新 $dp[i][j] = \max(dp[i][j], dp[i-1][j - \text{weight}[i]] + \text{cost}[i])$ * 初始化 : $dp[ i ][ j ] = 0,\quad \forall i = 0\sim n, ~j = 0\sim w$ * 時間複雜度 : 背包的範圍$w$，物品種類數量$N$，總共有 $Nw$ 個問題，因此時間複雜度為 $O(Nw)$ ---- ### 最長遞增子序列(LIS) 題序 : 從一連串的整數序列中選出最長的嚴格遞增子序列（strictly longest increasing subsequence） 例如：在 $\{1, 3, 2, 2, 4, 0\}$ 中 LIS 為 $1, 3, 4$ 或者 $1, 2, 4$ ---- 第一步 分割問題 : 記錄**第 $i$ 個元素為 LIS 的結尾**下的 LIS 長度 第二步 設計算法 : 每次檢查位置 $i$ 是否存在任何位置 $j$ $(j < i)$，則 $arr[i]$ 可以接在 $arr[j]$ 後面，$dp[i] = dp[j] +1$ ---- ```cpp int LIS(){ // 初始化。每一個元素本身就是長度為 1 的 LIS。 for (int i=0; i<N; i++) dp[i] = 1; for (int i=0; i<N; i++) // 找出 arr[i] 能接在哪些數字後面 // 若是可以接，長度就增加。 for (int j=0; j<i; j++) if (arr[j] < arr[i]) dp[i] = max(dp[i], dp[j] + 1); // dp[] 之中最大的值即為 LIS 的長度。 return *max_element(dp, dp+n); } ``` ---- * $dp[ i ]$ : 以 $arr[i]$ 為結尾的最長遞增子序列長度 * 測試每個字串結尾 $arr[ i ]$ * 狀態轉移方程：當有一個更好的方法是在同長度下可以獲得更長序列時，更新 : $dp[i]=\max(dp[i],dp[j]+1)$ * 初始化：$dp[i]=1$ $(1 \le i \le n)$ 至少選自己長度為 1 * 時間複雜度 : 狀態數 $O(N)$，轉移複雜度 $O(N)$，總複雜度 $O(N^2)$ ---- ### 最長共同子序列 (LCS) 題序 : 給定兩個字串 $s, t$，求 $s$ 與 $t$ 的最長共同子序列( Longest Common Subsequence ) ``` Input x = "ABCBDAB" y = "BDCABA" Output LCS = 4 ``` ---- ### 思路 第一步 分割問題：記錄在分別字串前綴 $s[0..i]$ 和 $t[0..j]$ 下的 LCS 長度 第二步 設計算法：每次檢查當前的結尾 $s[i]$ 是否與 $t[j]$ 一樣，若是一樣 則 $dp[ i ][ j ] = dp[ i-1 ][ j-1 ] + 1$ 否則 $dp[ i ][ j ]$ 就會等於 $\max(dp[i-1][j], dp[ i ][ j-1 ]$) ---- ### sample x = "ABCBDAB" y = "BDCABA"  ---- * $dp[i][j]$代表字串前綴$s_{0...i}$與$t_{0...j}$的LCS * 轉移式 : $dp[i][j]=\begin{cases}dp[i-1][j-1]+1,s[i]=t[j]\\ \max(dp[i-1][j],dp[i][j-1]),s[i]\ne t[j]\end{cases}$ * 初始化 : $dp[i][j]=0$ * 時間複雜度 : 狀態數$O(n^2)$，轉移複雜度$O(1)$，總複雜度$O(n^2)$ * 通常為了方便會把 $dp$ 陣列平移，且此 DP 可以滾動 (等等會講) ---- ### 路徑回朔 - 尋找哪一個才是合法的 LCS 時，紀錄每一個字串的選取 - 最後從 $len1$ , $len2$ 開始往前回溯，輸出最長公共子序列 ---- ### 範例代碼 ```cpp string ans; void trace(int x,int y){ if(!x&&!y) return ; if(tag[x][y]==0){ trace(x-1,y-1); ans += s[x-1]; } else if(tag[x][y]==1) trace(x-1,y); else trace(x,y-1); } void solve(){ cin >> s >> t; len1 = s.size(), len2 = t.size(); for(int i = 1; i <= l1; i++) tag[i][0]=1; for(int i = 1; i <= l2; i++) tag[0][i]=-1; for (int i = 1; i <= l1; i++) { for (int j = 1; j <= l2; j++) { if (s[i-1] == t[j-1]) { dp[i][j] = dp[i-1][j-1] + 1; tag[i][j] = 0; } else if(dp[i-1][j]>=dp[i][j-1]){ dp[i][j] = dp[i-1][j]; tag[i][j] = 1; } else{ dp[i][j]=dp[i][j-1]; tag[i][j] = -1; } } } cout << dp[len1][len2] << "\n"; trace(len1,len2); reverse(ans.begin(), ans.end()); cout << ans << endl; } ``` --- ## DP 優化 ---- ### 時間上的優化 - 有非常多的種類，分別用在不同的情況 - 單調隊列優化、斜率優化、四邊形優化、分治優化、矩陣快速冪、多項式乘法、aliens 優化... - 由於是進階內容，本堂課程內容著重於讓大家認識 DP 以及可以靠自己列出轉移式，因此本堂沒有要教，若已熟知基礎 DP 內容或是對以上優化有興趣都可以再來敲我們問 ---- ### 空間上的優化 ### 滾動 DP 很直覺的優化方式之一 - 滾動 DP 的作用在於優化空間 - DP 題目經常是需要用到的是線性的解 - 由於前面的解往往不用紀錄，可以用滾動 DP 優化 - 通常可以直接壓掉一個維度的大小 ex: $dp[N][M] \to dp[N]$ ---- 拿遞迴數學式來舉例 $f(n)=f(n-1)+f(n-2)$ - 計算每一項在計算時，只會用到$dp[n],dp[n-1],dp[n-2]$ - 只能用 bottom-up 計算 - 只需要三個變數交替使用 $cur,pre,ppre$ ```cpp int cur, pre = 1, ppre = 0; for(int i = 2; i <= n; i++) cur = pre + ppre, ppre = pre, pre = cur; ``` ----  ---- ### 滾動 DP 結論 - 用來節省空間，常常可以節省一個維度 - 不是所有 DP 都可以滾動 - 用於 bottom-up，單次計算 - 從轉移式中看計算每一項所需要用到的子狀態是否有跟著遞增 (算到後面，前面的狀態就不會再被使用) ---- ### 直接實作最後一題 : 二階樓梯記數問題 一個 $n\times n$ 方格棋盤，從左上角走到右下角，每次只能往右走一格或者往下走一格。請問有幾種走法？ example :  ---- 第一步 分割問題：會發現對於任何一個方格來說，只可能「從上走來」或者「從左走來」，答案是兩者相加，也就是說可以從上方以及左方的方格步數推算出當前這格的步數 第二步 設計轉移式：$dp[i][j]$ 代表走到當前 $(i,j)$ 格有幾種方法，因此 $$ dp[i][j] = dp[i-1][j] + dp[i][j-1] $$ ---- 發現轉移式只需要用到 $i$ 的前一項或者是 $j$ 的前一項 那是否可以節省空間呢? 答案是當然，如果不需要儲存所有問題的答案，只想要得到其中一個特定問題的答案，那只需要一維陣列就夠了，也就是 $O(N)$ 空間 <!-- .element: class="fragment" data-fragment-index="1" --> ---- 舉 $n=3$ 為例，想像對平面做投影，就會壓縮成右圖 此時我們對陣列分別依序做 a,b,c 的轉移就會相當於原圖的轉移做完 <div style="position: absolute; left: 0%; top:100%;">  </div> <div style="position: absolute; right: 0%; top:100%;"> <br> <br> <br>  </div> ---- 如此一來就成功的作出了空間優化了 ```cpp for (int i = 1; i < N; i++) for (int j = 1; j < N; j++) f[j] += f[j - 1]; ``` ---- ### 注意 有時候滾動時可能會汙染到原本的資料， 所以在壓維度時要想清楚壓哪個維度 --- ### 總結 DP 是個博大精深的演算法，初學者剛學演算法很快就會碰到 然而難的 DP 也可以到變成防破台||(~~防~~)|| :fearful: DP 不論從難度、類型來看，變化都非常多 ---- 以前幾乎所有競賽 DP 都扮演很重要的角色(~~以前台灣站更是每年 DP 占了都 1/3 的題數~~)，也因此好好學會 DP 非常的重要! ---- DP 不算是一個制式的演算法，而是一種概念，因此它的用途/形式多變想學好它不是很容易，要能在在看到題目時有辦法快速辨別能不能 DP / 怎麼 DP 等只能靠多看題目多練習 (把各種類型的 DP 都看很多次自然而然就會熟悉模式了(O)) :poop: --- ## 練習 & 問問題時間 [Link](https://vjudge.net/contest/772302)