--- ###### tags: `2020 師大附中校隊培訓` --- # 基礎動態規劃 ## 2020 師大附中校隊培訓 #### joylintp #### 10.27.2020 --- ## 用子問題的解算出大問題的答案 --- ## 走樓梯 有 $N$ 階樓梯， 每次可以走 1 階或 2 階， 求走完 $N$ 階樓梯的方法數除以 $10^9+7$ 的餘數 ---- ### 除以 $10^9+7$ 的餘數 * $(a+b)\ \%\ c=(a\ \%\ c+b\ \%\ c)\ \%\ c$ * $(a-b)\ \%\ c=(a\ \%\ c-b\ \%\ c + c)\ \%\ c$ * $(a\times b)\ \%\ c=(a\ \%\ c\times b\ \%\ c)\ \%\ c$ * $(\frac{a}{b})\ \%\ c=(a \times b^{c-2})\ \%\ c$ （$c$ 為質數） （非質數除法需使用擴展歐幾里得） ---- 令 $dp_i$ 為走 $i$ 階的方法數 $dp_i= \begin{cases} 1 & ,0 \le i \le 1 \\ dp_{i-1} + dp_{i-2} & ,i \ge 2 \end{cases}$ --- ## 青蛙 1 ### AtCoder Educational DP Contest pA 有 $N$ 顆石頭，第 $i$ 顆石頭的高度為 $h_i$， 目前青蛙停在第 1 顆石頭上 當青蛙停在第 $i$ 顆石頭上時， 可以跳到第 $j\ (i+1 \le j \le i+2)$ 顆石頭， 花費的體力為 $|h_i-h_j|$ 求青蛙跳到第 $N$ 顆石頭需要花費的體力總和最小值 ---- 令 $dp_i$ 為跳到第 $i$ 顆石頭時要花費的最少體力 $dp_i= \begin{cases} 0 & ,i=1 \\ |h_1-h_2| & ,i = 2 \\ min(dp_{i-2} + |h_i-h_{i-2}|, \\ dp_{i-1} + |h_i-h_{i-1}|) & ,i>2 \end{cases}$ 時間複雜度 $O(N)$ --- ## 青蛙 2 ### AtCoder Educational DP Contest pB 有 $N$ 顆石頭，第 $i$ 顆石頭的高度為 $h_i$， 目前青蛙停在第 1 顆石頭上 當青蛙停在第 $i$ 顆石頭上時， 可以跳到第 $j\ (i+1 \le j \le min(N, i+K))$ 顆石頭， 花費的體力為 $|h_i-h_j|$ 求青蛙跳到第 $N$ 顆石頭需要花費的體力總和最小值 ---- 令 $dp_i$ 為跳到第 $i$ 顆石頭時要花費的最少體力 $dp_i= \begin{cases} 0 & ,i=1 \\ |h_1-h_2| & ,i = 2 \\ min\{dp_{i-j} + |h_i-h_{i-j}|\ |\\\ 1 \le j \le min(i,K)\} & ,i>2 \end{cases}$ 時間複雜度 $O(NK)$ --- ## 假期 ### AtCoder Educational DP Contest pC 有 $N$ 天的假期 每天可以選游泳、爬山、在家其中一個， 第 $i$ 天做這些事分別可以得到 $a_i,b_i,c_i$ 的滿足度， 求在不連續兩天選一樣的情況下，可能的總滿足度最大值 ---- 令 $dp_{ij}$ 為第 $i$ 天做第 $j$ 件事時最高的滿足度 $dp_{i0}= \begin{cases} a_1 & ,i=1 \\ max(dp_{i-1\ 1}, dp_{i-1\ 2}) + a_i& ,i > 1 \end{cases}$ 剩餘兩活動同理，答案為 $max(dp_{n\ 0}, dp_{n\ 1}, dp_{n\ 2})$ 時間複雜度 $O(N)$ --- ## 01 背包問題 有 $N$ 樣物品， 每個物品有自己的價值 $p_i$ 和重量 $w_i$ 現在有一個耐重 $k$ 的背包， 問在所有物品只能選擇全放進背包或全不放進背包的情況下， 背包內的物質總價值最高是多少？ ---- ### 重量 ### AtCoder Educational DP Contest pD ```cpp= for (int i = 1; i <= N; i++) { int w, v; cin >> w >> v; for (int j = 0; j < w; j++) dp[i][j] = dp[i - 1][j]; for (int j = W; j - w >= 0; j--) dp[i][j] = max(dp[i - 1][j - w] + v, dp[i - 1][j]); } int ans = 0; for (int i = 0; i <= W; i++) ans = max(ans, dp[N][i]); ``` 時間複雜度 $O(NW)$ ---- ### 價值 ### AtCoder Educational DP Contest pE ```cpp= for (int i = 1; i <= 100000; i++) dp[i] = 1e18; int sum = 0; for (int i = 1; i <= N; i++) { int w, v; cin >> w >> v; sum += v; for (int j = sum; j >= v; j--) dp[j] = min(dp[j], dp[j - v] + w); } for (int i = sum; i >= 0; i--) if (dp[i] <= W) cout << i << '\n', exit(0); ``` 時間複雜度 $O(N\ \Sigma v)$ --- ## 最長共同子序列（LCS） ---- ### 子序列 字串 $S'$ 為字串 $S$ 的子序列若 $S'$ 可以透過刪除 $S$ 中若干字元得到 `S = "ABCBDEAC"` `S` 的子序列: `"ABC"`、`"AAC"`、`""` 不是 `S` 的子序列: `"DCBA"`、`"F"` 最長共同子序列即為兩字串共同子序列中長度最長者 ---- 令 $dp_{ij}$ 為考慮第一個字串前 $i$ 個字元與第二個字串前 $j$ 個字元的最長共同子序列 $dp_{ij}= \begin{cases} 0 & ,i=0\ or\ j=0 \\ dp_{i-1\ j-1} + 1 & ,i > 0,\ j > 0,\ S[i] = T[j] \\ max(dp_{i-1\ j-1}, dp_{i-1\ j}, dp_{i\ j-1}) & ,i > 0,\ j > 0,\ S[i] \ne T[j] \end{cases}$