# 中電會五月主題課程 # 基礎動態規劃 蔡孟廷 ting39 --- ## 自我介紹 handle: ting39 ---- ### 簡歷 * 台中一中電腦資訊研習社 教學長 * 2024 資訊奧林匹亞第一階段選訓營 結訓 * 2025 資訊奧林匹亞第一階段選訓營 結訓 * 112 學年度學科能力競賽決賽資訊科 三等獎 * 113 學年度學科能力競賽決賽資訊科 二等獎 * 2023 網際網路程式設計全國大賽(NPSC) 優勝 * 2023 HP codewars 第三名 * 2023 青年程式設計競賽(ISSC) 第二名 * 2024 青年程式設計競賽(ISSC) 第一名 ---- * Codeforces rating 1986  --- ## 動態規劃(DP)是什麼?  ----  ---- 動態規劃（英語：Dynamic programming，簡稱DP）是一種在數學、管理科學、電腦科學、經濟學和生物資訊學中使用的，通過把原問題分解為相對簡單的子問題的方式求解複雜問題的方法。 (節錄自維基百科) --- ## 漢堡王 ---- BBQ 培根牛肉堡 + 雙起士牛肉堡 + 小薯X2 ----  --- ## 晚餐吃什麼? ---- 1. 每一天吃不同食物有不同「爽度」 2. 不能兩天吃同樣的食物 3. 想要一個星期的爽度總和最高 ---- |吃啥|一|二|三|四|五|六|日| |:----:|:----:|:----:|:----:|:----:|:----:|:----:|:----:| |食也|100|50|65|80|105|100|55| |魚藏|80|70|60|60|100|35|6000| |忠武|70|10|60|85|45|50|65| ---- 有幾種組合? ---- $3\times 2^6=192$種 要算總共 $192\times 7=1344$ 次 ---- ### 事實上... 如果知道前6天怎麼吃最好，就會變得很好算! (或者前5、4、3...天) ----  ---- 只要計算$6\times 6=36$次！  --- ## 費式數列 $$ \begin{aligned} f_0&=0\\ f_1&=1\\ f_{n}&=f_{n-1}+f_{n-2} (n\geq 2) \end{aligned} $$ 輸入一個$n$$(1\leq n \leq 10^6)$，輸出$f_n \mod(1e9+7)$ ---- ### 最直觀的作法 遞迴! ```cpp= int mod=1e9+7; int f(int n){ if(n==0) return 0; else if(n==1) return 1; else return (f(n-1)+f(n-2))%mod; } ``` 直接把定義照抄上去就好了 ---- ### 複雜度分析  每一次呼叫函數都會再呼叫兩次 所以複雜度是$\text{O}(2^n)$ ---- ### 觀察  重複呼叫了! ---- ### 觀察 可以把運算結果儲存到陣列裡面，每次要用時再從陣列中拿 ---- ```cpp= vector<int> v(n); v[0]=0; v[1]=1; for(int i=2; i<n; i++){ v[i]=v[i-1]+v[i-2]; } ``` ---- ### 複雜度分析 for迴圈$\text{O}(n)$，其他$\text{O}(1)$ $$ \text{O}(n) $$ ---- ### dp的精神 將問題拆分，算過的東西不要再算。 --- > # 游擊戰與正規戰相配合，積小勝為大勝，以空間換取時間 > \-國民黨將領 白崇禧 --- ## [A - Frog 1](https://atcoder.jp/contests/dp/tasks/dp_a) ---- 有一隻青蛙和$n$個石頭，若青蛙現在在第$i$個石頭，可以選擇跳到第$i+1$或第$i+2$個石頭。第$i$個石頭的高度是$h_i$，從第$i$個石頭跳到第$j$個石頭需要花費$|h_i-h_j|$的體力。問從第$1$個石頭跳到第$n$個石頭的最小花費。 * $2\leq n\leq 10^5$ ---- 思考若現在在第$i$個石頭，**上一步**可能在哪裡。 ---- $i-1$或$i-2$ 因此只要計算哪一種選擇比較好就好 相當於把$i-1$和$i-2$的答案**轉移**到$i$ ---- 假設$dp_i$為從$1$跳到$i$的最小花費，則: $$ dp_i=min(dp_{i-1}+|h_i-h_{i-1}|,dp_{i-2}+|h_i-h_{i-2}|) $$ ---- ```cpp= vector<int> dp(n); dp[0]=0; dp[1]=dp[0]+abs(h[1]-h[0]); for(int i=2;i<n;i++){ dp[i]=min(dp[i-1]+abs(h[i]-h[i-1]),dp[i-2]+abs(h[i]-h[i-2])); } ``` ---- 最後答案就是$dp[n-1]$，複雜度$\text{O}(n)$ --- ## 對於dp的思考 ---- 1. 定義子問題:定義dp陣列的維度、參數、意義 2. 列出轉移式:dp[i]=? --- ## [F - LCS](https://atcoder.jp/contests/dp/tasks/dp_f) ---- 給定兩個字串$s$、$t$，求最長共同子序列。 * $|s|, |t|\leq 3000$ input: axyb abyxb output: axb ---- 先試著求長度 定義$dp[i][j]$為$s[0,i]$和$t[0,j]$的LCS長度，則有兩種可能: $s[i]=t[j]$:最後的字元相同，所以LCS拿這個字元一定會最好。 $s[i]\neq t[j]$:最後的字元不同，沒辦法拿這一組。 ---- 即是: $$ dp[i][j]= \begin{cases} dp[i-1][j-1]+1 & \text{if } s[i]=t[j]\\ max(dp[i-1][j],dp[i][j-1]) &otherwise \end{cases} $$ ---- ```cpp= int n=s.size(),m=t.size(); vector<vector<int>> dp(n,vector<int>(m)); dp[0][0]=(s[0]==t[0]); for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ if(s[i]==t[j]&&i>0&&j>0) dp[i][j]=dp[i-1][j-1]+1; if(i>0) dp[i][j]=max(dp[i][j],dp[i-1][j]); if(j>0) dp[i][j]=max(dp[i][j],dp[i][j-1]); } } ``` ---- 現在找出長度了，該怎麼還原解？ 一組解，就相當於對於解的每一個前綴都是那個長度的解 所以可以對dp表格內的每一個值另外再存他的**轉移來源**。 --- [CSES DP](https://cses.fi/problemset/) 據說全部寫完的話化學就會及格 [Atcoder DP contest](https://atcoder.jp/contests/dp/tasks)