Dynamic-Programming

Prefix table、edit operations、subsequence 與 interval palindrome DP

0/1、unbounded、reachability、counting 與 optimization state

路徑計數、成本最佳化、反向資源 DP 與局部幾何

LeetCode 940 解題筆記：依最後一個字元分類；以 c 結尾的不同子序列 = 目前所有不同子序列後面接 c，再加上 c 本身，直接覆蓋舊的值

LeetCode 2973 解題筆記：三個數的最大乘積只可能是「最大的三個」或「最小的兩個 × 最大的一個」；每個子樹只回傳最小 2 個和最大 3 個，後序合併

LeetCode 1246 解題筆記：區間 DP；arr[i] 自己刪、兩端相同時跟裡面一起刪，或切成兩段，三種取最小

LeetCode 1425 解題筆記：dp[i] = nums[i] + max(0, 前 k 個 dp 的最大值)；前 k 個 dp 的最大值是滑動視窗最大值，用單調佇列 O(1) 取得

LeetCode 1373 解題筆記：後序遍歷回傳 (總和, 最小值, 最大值, 是不是 BST)；左子樹的最大值 < 自己 < 右子樹的最小值才是 BST

LeetCode 996 解題筆記：n 最多 12，用 bitmask DP：dp[mask][last] = 用了 mask 這些數、最後一個是 last 的排列數；相同的數規定依 index 順序使用來去重

LeetCode 773 解題筆記：盤面只有 6! = 720 種，把盤面攤平成字串當 BFS 的狀態，0 跟相鄰格交換就是下一個狀態

LeetCode 2376 解題筆記：數位 DP，狀態 (pos, tight, started, mask)；mask 記錄用過的數字，前導零不能算成用過 0

LeetCode 2163 解題筆記：枚舉第一段和第二段的分界 k；左邊 nums[:k] 選 n 個最小的（最大堆維護），右邊 nums[k:] 選 n 個最大的（最小堆維護），前後綴各掃一次