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

Jurre Houtkamp on Unsplash

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

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

DP狀態轉移關係式

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

詮釋

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

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

長度為ｎ的序列解碼方法數
= 長度為n-1的序列解碼方法數 + 長度為n-2的序列解碼方法數 (在解碼１Ａ～２６Ｚ的前提下)

遞迴數列 配合 數列DP框架

合縱連橫: 從 數列DP 理解 遞迴數列的本質

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]

Subsets

一魚多吃 多角度切入 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[區間] = Max{ 拿i項物品的利益 - DP[對手的區間] }

= Max{ 拿1樣的局面獲得的利益, 拿2樣的局面獲得的利益, 拿i樣的局面獲得的利益, ...}

Stone Game

玩遊戲也可以用DP ? 石頭遊戲 Stone Game I 的最佳策略_Leetcode #877

Stone Game II

玩遊戲也能用DP? 石頭遊戲Stone Game II 的最佳策略+影片教學_Leetcode #1140

Stone Game III

用DP來玩遊戲 石頭遊戲 III_Stone Game III_Leetcode #1406

找零錢類(多重選擇，擇優選)

DP狀態轉移關係式 與 詮釋

DP[ amount ]

= 用題目給定的零錢coins去找零錢，看哪一種的找零錢方法所需要的銅板數量最少

= min{ DP[ amount - coin_i ] }, where coin_i is a valid coin

合縱連橫: 找零錢的DP框架_理解背後的本質

合縱連橫: 找零錢的DP框架_理解背後的本質

Coin Change

DP動態規劃 深入淺出 以Coin change最精簡找零 為例

Perfect Squares

一題多解 用DP、BFS去解 Pefect Square 完全平方數的化簡_Leetcode #279

DP[ amount, coin_index ]

= 用題目給定的零錢coins去找零錢，計算總共有多少種找零錢的組合方法數。

= DP[ amount, coin_index-1 ] + DP[ amount - coins[coin_index], coin_index],

where coin_index is index of a valid coin

Coin Change II

DP動態規劃 深入淺出 以Coin change II 找零方法數 為例

Combination Sum IV

化簡無所不在 用找零錢DP框架來解 組合數之和IV_Combinations Sum IV_Leetcode #377

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

DP狀態轉移關係式

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

詮釋

當下的最佳利益
= Max{ 選第i個物件情境下所能獲得的總體利益, 跳過不選第i個物件 情境下所能獲得的總體利益}

House Robber 系列題統整

合縱連橫: 從區間DP理解House Robbery系列題 背後的本質

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

House Robber III

舉一反三 用樹型DP思想來解 House Robbery III_Leetcode #337

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

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)走過來。

移動路徑 配合 格子點DP框架

合縱連橫: 從 移動路徑 理解 格子點DP 框架的本質。

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]}

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個

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[昨日持有現金]-今日股價 }

詮釋

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

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

Best time to buy and sell stock 全系列題

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

Minimum Cost to Cut a Stick

用DP來精打細算 切割木條的最小成本 Min Cost to Cut a Stick_Leetcode #1547

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

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

Longest Palindromic Subsequence 其實就是字串s和字串s頭尾顛倒的LCS

化簡無所不在 用LCS的DP模型解 最長回文子序列 Longest Palindromic Subseq_LC#516

圖論 最短路徑類 (或 最小成本路徑) Shortest Path

DP狀態轉移關係式 與詮釋

假如我們今要從節點i 走到節點j，怎麼走是最短路徑(或者 最小成本路徑)?

DP[i, j]

= min( DP[i, j], DP[i][k] + DP[k][j] )

如果原本 節點i 走到節點j 的路徑比較短，就維持原狀

如果 節點i 先走到 節點k 再走到節點j 的路徑比較短，就選擇這條更短的路徑。​

Minimum Cost to Convert String I 轉換字串的最小成本

圖論+DP: 字串轉換的最小成本 Min Cost to Convert String I_Leetcode #2976

Path with Maximum Probability 成功機率最高的路徑

🚗圖論+DP應用:最高成功機率的路徑 Path with Max Probability_Leetcode #1514