or
or
By clicking below, you agree to our terms of service.
New to HackMD? Sign up
Syntax | Example | Reference | |
---|---|---|---|
# Header | Header | 基本排版 | |
- Unordered List |
|
||
1. Ordered List |
|
||
- [ ] Todo List |
|
||
> Blockquote | Blockquote |
||
**Bold font** | Bold font | ||
*Italics font* | Italics font | ||
~~Strikethrough~~ | |||
19^th^ | 19th | ||
H~2~O | H2O | ||
++Inserted text++ | Inserted text | ||
==Marked text== | Marked text | ||
[link text](https:// "title") | Link | ||
 | Image | ||
`Code` | Code |
在筆記中貼入程式碼 | |
```javascript var i = 0; ``` |
|
||
:smile: | ![]() |
Emoji list | |
{%youtube youtube_id %} | Externals | ||
$L^aT_eX$ | LaTeX | ||
:::info This is a alert area. ::: |
This is a alert area. |
On a scale of 0-10, how likely is it that you would recommend HackMD to your friends, family or business associates?
Please give us some advice and help us improve HackMD.
Syncing
xxxxxxxxxx
Dynamic Programming
動態規劃
搞懂這些 一秒變成通靈大師
前言及核心概念
前言 – DP 是啥?
動態規劃。透過解決小問題組合成大問題的答案。
DP 題通常難以被其他算法取代,且題型多種多樣。
為什麼會說 DP 是通靈則是因為一定程度的題目通常轉移式都不好求,很吃你的直覺。
遇到DP題的頻率大概為 1-2 題/場,但 台灣站 3 題/場,因此若是你 DP 很強可以拿去說嘴很久。
核心概念 – DP的必知知識
[尋找問題分割方法]
通常在 DP 裡面,總是可以找到當前狀態的前幾個狀態合併成為當前狀態,而特性如下。
[把大問題遞迴分割成更小的問題]
根據以上幾點,尋找到問題之間的關係後,即可分割成小問題去進行求解,求解過程主要是對小問題進行解答後,在根據小問題的答案進行下一步操作。
[設計計算過程]
實作
分別有兩種方式
通靈的路上-認識DP
先看過兩題例題,為經典的記憶化搜索
例題Q1. 階乘求解
給你 \(q\) 次詢問 每次給定數字 \(n\) 詢問 \(n!\) 為多少
根據前面的步驟,會發現 \(n!\) 跟 \(n-1\) 的關係為 \((n-1)! * n\)
所以就可以分割問題為 \(1!,2!,3!,...,(n-1)!,n!\)
設計方法則為 每一層是前一層 \(\times\) 當前層數 [ \((n-1)! * n\) ]
實作方法則在下面做出簡單的範例
分析例題一的時間複雜度以及空間複雜度
時間複雜度 : 總共 N 個問題,每個問題花費 O(1) 時間,總共花費 O(N) 時間。
空間複雜度 : 求 1! 到 N!, 總共 \(N\) 個問題,用大小為 \(N\) 的陣列儲存全部問題的答案,空間複雜度 \(O(N)\)
例題Q2 遞迴數學式求解
\(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
Bottom-up
分析例題二的時間複雜度以及空間複雜度
時間複雜度 : 總共 \(N\) 個問題,每個問題花費 O(1) 時間,總共花費 O(N) 時間。
空間複雜度 : 求 \(1\) 到 \(N\),總共 \(N\) 個問題,用大小為 \(N\) 的陣列儲存全部問題的答案,空間複雜度 O(N)
Top-Down v.s. Bottom-Up
DP的時間/空間 複雜度&&轉移式
DP的時間/空間 複雜度
簡單的時間複雜度 : 狀態數*轉移複雜度
難的時間複雜度 : 根據每個人會有不同的實作方式去計算
狀態數 : 計算最終答案總共需要用到的子問題數量
轉移複雜度 : 計算任一個子問題的複雜度
空間複雜度 : 很直觀根據你開了多少來確定,應該不用太多描述。
DP的轉移式
範例
\(f(n)=f(n-1)+f(n-2)\) – 遞迴數學式問題
\(dp[i]=\max\limits_{0\le j\lt i,i-j<=k}\{dp[j]+a[i]\}\) – 單調隊列優化
\(dp[i][j]=\max({dp[i-1][j],dp[i-1][j-w[i]]+c[i]})\) 二維背包問題
\(dp[i]=max(dp[i],dp[j]+1),\forall arr[i] > arr[j]\land i > j\) LIS (最長遞增子序列)
\(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}\) LCS (最長公共子序列)
DP 的生命就是轉移式
下課時間
DP經典問題實戰
零錢問題
題序 : 身上帶太多的零錢會很麻煩,因此會希望店員在找零錢能夠以最少的硬幣數來找,而不是全部都用1元塞給我們。
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →也就是要用最少的硬幣數湊出目標數字,具體作法為比較「每個硬幣的面額」與「其次小硬幣的面額」
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →假設需要找$86
【情況1】硬幣有:$50, $10, $5, $1 四種面額,由於每個數字都是次小數字的倍數,因此可以直接用greedy寫掉,從最大的硬幣去選。答案為 50*1 + 10*3 + 5*1 + 1*1 總共六枚
【情況2】硬幣有:$50, $46, $10, $5, $1 五種面額,這時會發現greedy好像怪怪的,因此這時候就需要使用 [ 動態規劃 ] 去完成這題。
top-down
使用遞迴法,分割子問題
目標(原問題): 要算出 86 元的最少硬幣數量
有 $50, $46, $10, $5, $1 這些種類的硬幣
分割為子問題:
透過把大問題分解成更小的問題求解
過程中會發現同一個值 x 可能會出現很多次
以 76 為例:
如果每次 minimumChange(76) 都重新求解,則會花費很多時間
回到 DP 的核心概念
當分割出來的子問題,一而再、再而三出現,儲存這些問題的答案,避免重複求解,以空間換取時間。
DP 狀態: \(dp[ x ]\) - 紀錄目前要湊成金額 \(x\) 的最少硬幣數目。
狀態轉移:當用一個硬幣面額 coins[i] 可以使用更少的硬幣數目來湊成金額 x 時,更新
dp[
\(x\)] = min( dp[
\(x\)], dp[
\(x\)– coins[
\(i\)]] + 1)
時間複雜度
找錢的範圍為 \(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]\) 最少需要多少硬幣時,使用
coins[j]
更新dp[i + coins[j]] =
min( dp[i + coins[j]], dp[ i ] + 1 )
;時間複雜度 : 找錢的範圍 \(n\),零錢種類數量 \(m\),總共有 \(nm\) 個問題,因此時間複雜度為 \(O(nm)\)
背包問題
n 個物品儘量塞進背包裡面,令背包裡面的物品總價值最高。背包有重量限制 \(w\)。
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →這就是廣為人知的背包問題,其有許多變形,而本堂課將介紹最經典的 [ 0/1 背包問題 ] 「 0/1 」的意思是:每個物品只會放進背包零個或一個。一個物品要嘛整個不放進背包、要嘛整個放進背包。物品無法切割。
看到這種問題若沒學過直覺通常會是貪心,不管是貪心他的價值或是貪心他的 CP 值也好,在這種題目下面都是錯的。
0/1 背包問題的關鍵點,在於如何有效利用背包的剩餘重量,找出最好的物品組合方式。
第一步,分割問題。
然而分割問題的方式很簡單:對某一件物品來說,我們可以選擇放或不放;然後移去這件物品,縮小問題範疇。
一件物品不放進背包,背包價值不變、背包耐重不變;一件物品放進背包,背包價值上升、背包耐重下降。遞迴公式為:
\(c\) (\(n\), \(w\)) \(=\) \(max\)\(( c(n-1, w)\), \(c(n-1, w-weight[n])\) \(+\) \(cost[n]\) )
就可以依照這個遞迴公式去設計 top-down 的版本
過程中,dp[n][w] 這個狀態是可以記錄的,會不斷重複出現
而 bottom-up 的迴圈版本如下:
\(dp[ i ][ j ]\):紀錄使用前 \(i\) 個元素,背包重量使用了 \(j\) 的最大價值。
測試每個物品 \(weight[ i ]\) 放或不放
狀態轉移方程:當有一個更好的方法是在同重量下可以獲得更高價值時,更新 \(dp[i][j] = max(dp[i][j], dp[i-1][j - weight[i]] + value[i]);\)
初始化 : \(dp[ i ][ j ] = 0\) \(\forall i = 0\sim n, j = 0\sim w\)
時間複雜度 : 背包的範圍\(N\),物品種類數量\(M\),總共有 \(NM\) 個問題,因此時間複雜度為 \(O(NM)\)
最長遞增子序列(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,
範例代碼
\(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 )
第一步 分割問題,記錄在分別字串前綴 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 時,我們就需要紀錄每一個字串的選取,由於每次查找的是 \(dp[x-1][y]\) 跟 \(dp[x][y-1]\) 哪個長度更長。
最後從 \(len1\) , \(len2\) 開始往前回溯,輸出最長公共子序列。
範例代碼
DP 優化
時間上的優化
空間上的優化
滾動 DP 很直覺的優化方式之一
滾動數組的作用在於優化空間。因為 DP 題目是一個自底向上的擴展過程,我們常常需要用到的是線性的解,前面的解往往不用紀錄。所以用滾動數組優化是很有效的。利用滾動數組的話在N很大的情況下可以達到壓縮存儲的作用,通常可以直接壓掉一個維度的大小。
ex: dp[N][M] \(\to\) dp[N]
滾動 DP 結論
直接實作最後一題 : 二階樓梯記數問題
一個 \(n\times n\) 方格棋盤,從左上角走到右下角,每次只能往右走一格或者往下走一格。請問有幾種走法?

example :
第一步 分割問題 會發現對於任何一個方格來說,只可能「從上走來」或者「從左走來」,答案是兩者相加,也就是說可以從上方以及左方的方格步數推算出當前這格的步數。
設計轉移式 \(dp[i][j]\) 代表走到當前 \(i\), \(j\) 格有幾種方法,因此\(dp[i][j] = dp[i-1][j] + dp[i][j-1]\)
然後這時候就會發現,他的轉移式只需要用到 \(i\) 的前一項或者是 \(j\) 的前一項,那是否可以節省空間呢
答案是必然的,如果不需要儲存所有問題的答案,只想要得到其中一個特定問題的答案,那只需要一維陣列就夠了,也就是 O(N) 空間。
就成功的作出了空間優化了
總結
DP 是個博大精深的演算法,初學者剛學演算法很快就會碰到,然而難的 DP 也可以到變成防破台
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →DP 不算是一個制式的演算法,而是一種概念,因此它的用途/形式多變想學好它不是很容易,要能在在看到題目時有辦法快速辨別能不能 DP / 怎麼 DP 等只能靠多看題目多練習(把各種類型的 DP 都看很多次自然而然就會熟悉模式了(O))
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →