DP演算法框架 與 推薦的DP學習路徑 (持續更新中)

閱讀時間約 10 分鐘

起源: 究竟什麼是DP動態規劃?


費式數列類
(雖然簡單,但是要了解為何引入DP,DP的優點在哪)


DP狀態轉移關係式

DP[n] = DP[n-1] + DP[n-2]


詮釋

第n項 = 前兩項相加 = 第n-1項 + 第n-2項。

到第n階的方法 = 先到第n-1階 再踩一階,或者 先到第n-2階 再踩兩階。(在一次只能踩一階或兩階的前提下)

長度為n的序列解碼方法數
= 長度為n-1的序列解碼方法數 + 長度為n-2的序列解碼方法數 (在解碼1A~26Z的前提下)

raw-image


Fibonacci Number

DP動態規劃 深入淺出 以Fibonacci Number 費式數列 為例


Climbing Stairs

一魚多吃 用費式數列的DP模型來解 爬樓梯Climbing Stairs_Leetcode #70


N-th Tribonacci Number

活用DP: 泰伯納西數列的第n項 Leetcode #1137_精選75題


Min Cost Climbing Stairs

一魚多吃 用費式數列的模型來解 Min Cost Climbing Stairs_Leetcode #746_精選75題


Decode Ways

一魚多吃 用DP計算解碼的方法數 Decode Ways_Leetcode #91


取捨類(取/不取,做/不做...)


DP狀態轉移關係式 與 詮釋

DP[ i ]

= 包含物件i的子集合 和 不包含物件i的子集合

= DP[i-1] + nums[i] 和 DP[i-1]

一魚多吃 多角度切入 Subset 子集合生成 Leetcode #78


DP狀態轉移關係式 與 詮釋

DP[ i ]

= Max{ 解開現在第i道題目, 跳過第i道題目 }

= Max{ questions[i][0] + DP[ i + questions[i][1] + 1 ], DP[ i+1 ] }


Solving Questions With Brainpower

用取捨DP來考高分 Solving Questions With Brainpower_Leetcode #2140



打家劫舍類(相鄰的物件不可同時選擇)


DP狀態轉移關係式

DP[i] = Max{ DP[i-2] + value[i], DP[i-1] + 0 }


詮釋

當下的最佳利益 = Max{ 選第i個物件,跳過不選第i個物件 }

raw-image

raw-image


House Robber

一魚多吃 用DP解House Robbery 打家劫舍問題_Leetcode #198_Leetcode 精選75題解析


Delete and Earn

化簡無所不在 用學過的DP模型解Delete and Earn 取捨之下的最高分數_Leetcode #740


House Robber II

化簡無所不在 用學過的DP模型解House Robbery II



房屋著色類(相鄰的房屋不可著同樣顏色)


DP狀態轉移關係式 與 詮釋

DP[i, prevColor]代表第i棟房屋~最後一棟房屋的最小著色成本

= min{ 第i棟房屋房屋選一個不和前一棟重複的顏色著色,接著考慮下一棟 }

= min{ costs[i][color] + DP[i+1, color] where color != prevColor }


Paint House

用取捨DP框架來上色 粉刷房屋I_Paint House_Leetcode #256


遞增/遞減子序列、遞增/遞減數列類

(符合特定規則的子序列、數列)


DP狀態轉移關係式

DP[ i ] = max( DP[i], DP[ k ] + 1 ), where k < i and nums[k] < nums[i]


詮釋

當下index i 的最長遞增子序列

= Max{ 原本的子序列長度,從前面比較小的數字nums[k]延伸過來的長度 }


Longest Increasing Subsequence

步步高升 最長遞增子序列 Longest Increasing Subsequence_DP_Leetcode #300


Number of Longest Increasing Subsequence

化簡無所不在 用學過的DP模型解Num of Longest Increasing Subsequence_LC#673



DP狀態轉移關係式

DP[ cur ][ diff ] = DP[ before ][ diff ] + 1,
where diff = nums[cur] - nums[before]


詮釋

後項-前項伴隨著公差diff,等差數列再延伸,長度+1


Longest Arithmetic Subsequence

用DP框架來思考 最長的等差數列Longest Arithmetic Subsequence_Leetcode#1027


DP狀態轉移關係式

DP[ cur ] = DP[ cur - diff ] + 1,

where diff = 給定的公差


詮釋

後項-前項伴隨著公差diff,等差數列再延伸,長度+1

Longest Arithmetic Subsequence of Given Difference

化簡無所不在 用數列DP來解 給定公差的最長等差數列 Leetcode #1218


路徑探索 (格子點DP)類

(在方格棋盤/格子點之中尋找路徑)


DP狀態轉移關係式 (在每回合只能往右走一格,往下走一格的前提下)

DP[y][x] = DP[y][x-1] + DP[y-1][x] 古典陣列式的寫法

DP[x, y] = DP[x-1, y] + DP[x, y-1] 比較直覺的pair+字典寫法


詮釋

(x, y)當下這個格子點,可以從上面(x, y-1)走過來,可以從左邊(x-1, y)走過來。

raw-image


Unique Paths

DP動態規劃 深入淺出 以Unique Path 路徑總數 為例_精選75題


Unique Paths II

DP動態規劃 深入淺出 以Unique Path II 路徑總數II 為例


DP狀態轉移關係式 (在每回合只能往右走一格,往下走一格的前提下) 與詮釋

走到(x, y)的最小成本

= DP[y][x]

= (x, y)本身的成本 + 前一步的最小成本

= grid[x, y] + min{ 前一步的可能情況 }

= grid[x, y] + min{ 走到左邊一格的最小成本, 走到上方一格的最小成本}

= grid[y][x] + min{ DP[y][x-1], DP[y-1][x] } 傳統的陣列表示法


Minimum Path Sum

用DP框架來思考 Minimum Path Sum 最小路徑成本總和_Leetcode #64



DP狀態轉移關係式 與 詮釋(只能下墜到左下方、正下方、右下方的前提下)

DP[y][x] = 從最上方下墜到matrix[y][x]的最小路徑成本

=[y][x]本身這格的成本 + min{ 從上方那一排下墜的成本 }

= matrix[y][x] + min{ DP[y-1][x-1], DP[y-1][x], DP[y-1][x+1]}


raw-image


Minimum Falling Path Sum

一魚多吃 用DP解最小成本的下墜路徑和 Minimum Falling Path Sum_Leetcode #931




DP狀態轉移關係式 (巴斯卡三角形的生成)

C(n, k) = C(n-1, k-1) + C(n-1, k) 組合數學的基本定理

DP[n][k] = DP[n][k-1] + DP[n-1][k]

詮釋

n個物品選k個 = 第n號物品有選中,剩下的選k-1個 + 第n號物品沒選中,剩下的選k個


raw-image



Pascal's Triangle

DP動態規劃 深入淺出 以Pascal Triangle 巴斯卡三角形 為例_Leetcode #118


Pascal's Triangle II

DP動態規劃 深入淺出 以Pascal's Triangle II 巴斯卡三角形 II為例



交易模擬(股票買賣、最小成本、最大獲利...) 類


限制只做多,在數個交易日中買賣獲得最大價差利潤


DP狀態轉移關係式

DP[ 今日持有現金 ] = Max{ DP[昨日持有現金], DP[昨日持有股票]+今日股價}

DP[ 今日持有股票 ] = Max{ DP[昨日持有股票], DP[昨日持有現金]-今日股價 }


詮釋

今天持有現金: 要嘛昨天就已經持有現金,要嘛今天才賣股票

今天持有股票: 要嘛昨天就已經持有股票,要嘛今天才買股票


raw-image


Best time to buy and sell stock 全系列題

合縱連橫: 從DP框架理解 最佳股票買賣系列題 的背後本質


給定旅行日期,和火車套票票價,計算最小旅行支出非用



DP狀態轉移關係式 與詮釋

假如我們今天要出遊有那些選擇?

其實就是三種選擇,

第一種是買一日票,只能覆蓋今天
第二種是買七日票,可以覆蓋最靠近的連續七天
第三種是買30日票(月票),可以覆蓋最靠近的連續三十天


我們要做的就是從這三種選擇裡面,

挑一個能夠盡量覆蓋出遊日期,又兼顧支出費用最小的選擇

DP[ day ]
= min( 一日票 + DP[ day-1], 七日票 + DP[day-7], 30日票 + DP[ day-30] )


Minimum Cost For Tickets

用DP來精打細算 火車旅行支出的最小費用_Leetcode #983 最佳化DP應用



共同子序列類 (Longest Common Subsequence)


DP狀態轉移關係式 與詮釋

LCS(Sa, Ta) = LCS(S, T) + 1 字尾相同,可以向前延伸

LCS(Sa, Tb) = Max{ LCS(Sa, T), LCS(S, Tb) } 字尾相異,只能捨棄當下字尾


Longest Common Subsequence

DP經典應用: 找出 最長共同子序列的長度 LCS_Leetcode #1143_Leetcode 精選75題解析


Uncrossed Lines 就是數字版本的LCS

化簡無所不在 用LCS的DP模型解Uncrossed Lines_Leetcode #1035

58會員
345內容數
由有業界實戰經驗的演算法工程師, 手把手教你建立解題的框架, 一步步寫出高效、清晰易懂的解題答案。 著重在讓讀者啟發思考、理解演算法,熟悉常見的演算法模板。 深入淺出地介紹題目背後所使用的演算法意義,融會貫通演算法與資料結構的應用。 在幾個經典的題目融入一道題目的多種解法,或者同一招解不同的題目,擴展廣度,並加深印象。
留言0
查看全部
發表第一個留言支持創作者!
你可能也想看
迎新活動「方格新手村」:新格友註冊加入方格子,知名日料吃到飽餐券送給你! 👉 還不是 vocus 的會員嗎?點此註冊,參與新手村活動 👈 近期站上也出現了不少新格友,為了歡迎各位的加入,「方格新手村」隨之登場! 即日起,只要是新註冊帳號於活動期間內發佈 3 則文章,就有機會抽獎獲得知名日料吃到飽餐券。原格友也可以一起同樂,我們準備了小任
Thumbnail
2024-06-21
93
《D.P:逃兵追緝令》S1 & S2~無能為力,要想改變,必有犧牲對2021年底播出的《D.P:逃兵追緝令》S1情節已記不清,得悉S2劇情發展與上季內容緊密相連,心想兩季才12集,每集約45分鐘,相對篇幅較短,決定從頭看一回,喜歡的題材,想細心欣賞。看畢感覺最深刻是,〝無能為力,要想改變,必有犧牲。〞
Thumbnail
2023-08-11
12
看鼠鼠的性行为,我能学到什么?生物学性差异的研究的规则脉络(DP·G&S-31)据说,发表给听众带来了巨大的冲击,发表现场也陷入了混乱。观察鼠鼠的性行为,对科学知识探索,尤其是生物学的范式发生了巨大转变。
Thumbnail
雌激素?快让睾丸也产一些!-从内分泌到社会性别差异(DP·G&S-30)是睾丸让人类变得充满攻击力么?母狮子不认为是这样的。 性激素是20世纪初发现的物质,产生了新的性内分泌学Sex Endocrinology分支学科。 性激素从化学物质的层面重组了将性差异只局限于身体结构的现有说明。
Thumbnail
企鹅会卖淫,不代表人类出卖身体具有自然性-社会生物学的社会偏见。(DP·G&S-29)1社会生物学 社会生物学的登场和定义社会生物学Sociobiology是寻找性差异生物学基础的尝试中最活跃的研究,也是大众所熟知的工作。 社会生物学这一用语广为人知的契机是通过美国哈佛大学生物学系教授爱德华·奥斯本·威尔森(Edward Osborne Wilson,1929年6月10日-2021年
Thumbnail
摸脑壳的科学—生物学性差异研究历史实例(DP·G&S-28)19世纪的科学家试图证明男性脑力更优越的结果是——食蚁兽比人类聪明。
Thumbnail
画不出不同生殖器的文艺复兴画家——世界观的变化和两种性的登场(DP·G&S-27)莎士比亚时期最权威的解剖学家将阴道视为内部阴茎,将阴唇视为包皮,将子宫视为阴囊,将卵巢视为睾丸。画家们:····· 那,这么画好了。今天的内容可能依然对温和的读者有些考验。但是请知悉:正视历史很重要。
Thumbnail
男女有别是科学的?再想想看呢?(DP·G&S-26)关于男女差异,我们所知道的知识是以什么为根据的? 本章通过具体事例对男女差异知识,特别是生物学知识的历史进行探讨。 科学地发现并正当地承认今天被认为是理所当然的所谓两个性别的差异知识,事实上并不是很久以前的事情。
Thumbnail
CLOUDWAYS 伺服器方案評比 - linode / VULTR-HF / Digital Ocean-DP《CLOUDWAYS 是什麼?》 測速說明 參賽主機: linode ☞ RAM 1GB方案,機房位置為 Tokyo VULTR ☞ High frequency + RAM 1GB方案,機房位置為 Tokyo 測試內容: 後台操作速度☞區塊編輯器以及OXYGEN Builder 測試工具:
Thumbnail
2022-05-25
5
《D.P:逃兵追緝令》觀後感:當暴力被習慣,我們也將失去反抗的力量。 「你知道我們部隊用的水壺吧?你知道上面寫了什麼嗎?1953,從韓戰的時候就在用了,連水壺都沒換了,怎麼可能改變?」曹石峰(趙賢哲飾)苦笑著說。 這一幕在我腦海中久久不能散去,深深的無力感襲來,令人窒息。比起華麗的動作戲、刺激的追捕過程,看完《D.P:逃兵追緝令》後,更直擊靈魂。
Thumbnail
2021-09-17
2
《D.P : 逃兵追緝令》-- 沉痛且發人深省預告中看似輕鬆趣味的題材,實則黑暗沉重,直指現實陰暗面,《D.P : 逃兵追緝令》裡透過悲劇性的故事以極具批判力道的方式呈現軍隊內長期以來存在的陋習與霸凌問題,再再衝擊世人的內心,也讓韓國時有所聞的逃兵與軍中霸凌議題再次浮上檯面。
Thumbnail
2021-09-01
4
迎新活動「方格新手村」:新格友註冊加入方格子,知名日料吃到飽餐券送給你! 👉 還不是 vocus 的會員嗎?點此註冊,參與新手村活動 👈 近期站上也出現了不少新格友,為了歡迎各位的加入,「方格新手村」隨之登場! 即日起,只要是新註冊帳號於活動期間內發佈 3 則文章,就有機會抽獎獲得知名日料吃到飽餐券。原格友也可以一起同樂,我們準備了小任
Thumbnail
2024-06-21
93
《D.P:逃兵追緝令》S1 & S2~無能為力,要想改變,必有犧牲對2021年底播出的《D.P:逃兵追緝令》S1情節已記不清,得悉S2劇情發展與上季內容緊密相連,心想兩季才12集,每集約45分鐘,相對篇幅較短,決定從頭看一回,喜歡的題材,想細心欣賞。看畢感覺最深刻是,〝無能為力,要想改變,必有犧牲。〞
Thumbnail
2023-08-11
12
看鼠鼠的性行为,我能学到什么?生物学性差异的研究的规则脉络(DP·G&S-31)据说,发表给听众带来了巨大的冲击,发表现场也陷入了混乱。观察鼠鼠的性行为,对科学知识探索,尤其是生物学的范式发生了巨大转变。
Thumbnail
雌激素?快让睾丸也产一些!-从内分泌到社会性别差异(DP·G&S-30)是睾丸让人类变得充满攻击力么?母狮子不认为是这样的。 性激素是20世纪初发现的物质,产生了新的性内分泌学Sex Endocrinology分支学科。 性激素从化学物质的层面重组了将性差异只局限于身体结构的现有说明。
Thumbnail
企鹅会卖淫,不代表人类出卖身体具有自然性-社会生物学的社会偏见。(DP·G&S-29)1社会生物学 社会生物学的登场和定义社会生物学Sociobiology是寻找性差异生物学基础的尝试中最活跃的研究,也是大众所熟知的工作。 社会生物学这一用语广为人知的契机是通过美国哈佛大学生物学系教授爱德华·奥斯本·威尔森(Edward Osborne Wilson,1929年6月10日-2021年
Thumbnail
摸脑壳的科学—生物学性差异研究历史实例(DP·G&S-28)19世纪的科学家试图证明男性脑力更优越的结果是——食蚁兽比人类聪明。
Thumbnail
画不出不同生殖器的文艺复兴画家——世界观的变化和两种性的登场(DP·G&S-27)莎士比亚时期最权威的解剖学家将阴道视为内部阴茎,将阴唇视为包皮,将子宫视为阴囊,将卵巢视为睾丸。画家们:····· 那,这么画好了。今天的内容可能依然对温和的读者有些考验。但是请知悉:正视历史很重要。
Thumbnail
男女有别是科学的?再想想看呢?(DP·G&S-26)关于男女差异,我们所知道的知识是以什么为根据的? 本章通过具体事例对男女差异知识,特别是生物学知识的历史进行探讨。 科学地发现并正当地承认今天被认为是理所当然的所谓两个性别的差异知识,事实上并不是很久以前的事情。
Thumbnail
CLOUDWAYS 伺服器方案評比 - linode / VULTR-HF / Digital Ocean-DP《CLOUDWAYS 是什麼?》 測速說明 參賽主機: linode ☞ RAM 1GB方案,機房位置為 Tokyo VULTR ☞ High frequency + RAM 1GB方案,機房位置為 Tokyo 測試內容: 後台操作速度☞區塊編輯器以及OXYGEN Builder 測試工具:
Thumbnail
2022-05-25
5
《D.P:逃兵追緝令》觀後感:當暴力被習慣,我們也將失去反抗的力量。 「你知道我們部隊用的水壺吧?你知道上面寫了什麼嗎?1953,從韓戰的時候就在用了,連水壺都沒換了,怎麼可能改變?」曹石峰(趙賢哲飾)苦笑著說。 這一幕在我腦海中久久不能散去,深深的無力感襲來,令人窒息。比起華麗的動作戲、刺激的追捕過程,看完《D.P:逃兵追緝令》後,更直擊靈魂。
Thumbnail
2021-09-17
2
《D.P : 逃兵追緝令》-- 沉痛且發人深省預告中看似輕鬆趣味的題材,實則黑暗沉重,直指現實陰暗面,《D.P : 逃兵追緝令》裡透過悲劇性的故事以極具批判力道的方式呈現軍隊內長期以來存在的陋習與霸凌問題,再再衝擊世人的內心,也讓韓國時有所聞的逃兵與軍中霸凌議題再次浮上檯面。
Thumbnail
2021-09-01
4