起源: 究竟什麼是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動態規劃 深入淺出 以Fibonacci Number 費式數列 為例
一魚多吃 用費式數列的DP模型來解 爬樓梯Climbing Stairs_Leetcode #70
活用DP: 泰伯納西數列的第n項 Leetcode #1137_精選75題
一魚多吃 用費式數列的模型來解 Min Cost Climbing Stairs_Leetcode #746_精選75題
一魚多吃 用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[區間] = Max{ 拿i項物品的利益 - DP[對手的區間] }
= Max{ 拿1樣的局面獲得的利益, 拿2樣的局面獲得的利益, 拿i樣的局面獲得的利益, ...}
玩遊戲也可以用DP ? 石頭遊戲 Stone Game I 的最佳策略_Leetcode #877
玩遊戲也能用DP? 石頭遊戲Stone Game II 的最佳策略+影片教學_Leetcode #1140
用DP來玩遊戲 石頭遊戲 III_Stone Game III_Leetcode #1406
找零錢類(多重選擇，擇優選)
DP狀態轉移關係式 與 詮釋
DP[ amount ]
= 用題目給定的零錢coins去找零錢，看哪一種的找零錢方法所需要的銅板數量最少
= min{ DP[ amount - coin_i ] }, where coin_i is a valid coin
DP動態規劃 深入淺出 以Coin change最精簡找零 為例
一題多解 用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
DP動態規劃 深入淺出 以Coin change II 找零方法數 為例
化簡無所不在 用找零錢DP框架來解 組合數之和IV_Combinations Sum IV_Leetcode #377
打家劫舍類(相鄰的物件不可同時選擇)
DP狀態轉移關係式
DP[i] = Max{ DP[i-2] + value[i], DP[i-1] + 0 }
詮釋
當下的最佳利益
= Max{ 選第i個物件情境下所能獲得的總體利益, 跳過不選第i個物件 情境下所能獲得的總體利益}
合縱連橫: 從區間DP理解House Robbery系列題 背後的本質
一魚多吃 用DP解House Robbery 打家劫舍問題_Leetcode #198_Leetcode 精選75題解析
化簡無所不在 用學過的DP模型解Delete and Earn 取捨之下的最高分數_Leetcode #740
化簡無所不在 用學過的DP模型解House Robbery II
舉一反三 用樹型DP思想來解 House Robbery III_Leetcode #337
房屋著色類(相鄰的房屋不可著同樣顏色)
DP狀態轉移關係式 與 詮釋
DP[i, prevColor]代表第i棟房屋~最後一棟房屋的最小著色成本
= min{ 第i棟房屋房屋選一個不和前一棟重複的顏色著色，接著考慮下一棟 }
= min{ costs[i][color] + DP[i+1, color] where color != prevColor }
用取捨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動態規劃 深入淺出 以Unique Path 路徑總數 為例_精選75題
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] } 傳統的陣列表示法
用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]}
一魚多吃 用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個
DP動態規劃 深入淺出 以Pascal Triangle 巴斯卡三角形 為例_Leetcode #118
DP動態規劃 深入淺出 以Pascal's Triangle II 巴斯卡三角形 II為例
交易模擬(股票買賣、最小成本、最大獲利...) 類
限制只做多，在數個交易日中買賣獲得最大價差利潤
DP狀態轉移關係式
DP[ 今日持有現金 ] = Max{ DP[昨日持有現金], DP[昨日持有股票]+今日股價}
DP[ 今日持有股票 ] = Max{ DP[昨日持有股票], DP[昨日持有現金]-今日股價 }
詮釋
今天持有現金: 要嘛昨天就已經持有現金，要嘛今天才賣股票
今天持有股票: 要嘛昨天就已經持有股票，要嘛今天才買股票
Best time to buy and sell stock 全系列題
用DP來精打細算 切割木條的最小成本 Min Cost to Cut a Stick_Leetcode #1547
給定旅行日期，和火車套票票價，計算最小旅行支出非用
DP狀態轉移關係式 與詮釋
假如我們今天要出遊，有那些選擇?
其實就是三種選擇，
第一種是買一日票，只能覆蓋今天。
第二種是買七日票，可以覆蓋最靠近的連續七天。
第三種是買30日票(月票)，可以覆蓋最靠近的連續三十天。
我們要做的就是從這三種選擇裡面，
挑一個能夠盡量覆蓋出遊日期，又兼顧支出費用最小的選擇。
DP[ day ]
= min( 一日票 + DP[ day-1], 七日票 + DP[day-7], 30日票 + DP[ day-30] )
用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) } 字尾相異，只能捨棄當下字尾
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 成功機率最高的路徑
