Dynamic-Programming

LeetCode 32 解題筆記：堆疊存索引，底部放目前這段合法括號開始前的位置，長度是 i - stack[-1]

LeetCode 834 解題筆記：換根 DP：先以 0 為根算子樹大小和 ans[0]，再用 ans[child] = ans[parent] - size + (n - size) 推到每個節點

LeetCode 2858 解題筆記：換根 DP：先算以 0 為根要翻幾條邊，根移到小孩時，這條邊原本順向就 +1、逆向就 -1

LeetCode 968 解題筆記：後序貪心，每個節點三種狀態：有相機、被覆蓋、沒被覆蓋；有小孩沒被覆蓋才放相機，最後根沒被覆蓋要補一台

LeetCode 1372 解題筆記：每個節點回傳兩個值：從這裡先往左、先往右的最長 zigzag；往左走接的是左小孩「先往右」的值

LeetCode 124 解題筆記：DFS 回傳往下的一條鏈，在每個節點用「左鏈 + 自己 + 右鏈」更新答案；負的鏈要丟掉

LeetCode 1186 解題筆記：Kadane 加一個狀態：結尾在這裡、還沒刪過 / 已經刪過一個；答案要在每一步都更新

一維 DP、狀態機 DP、DP + 單調佇列、排序後的區間排程 DP、子序列計數去重，以及標了 DP 但用觀察或貪心更快的題目

區間 DP（枚舉最後一步 / 兩端合併）、切成 k 段的分割 DP、回文表 + 分割，以及狀態太複雜時直接記憶化搜尋整個狀態

LeetCode 1220 解題筆記：狀態機 DP，狀態是最後一個母音；把「誰後面可以接誰」反過來寫成「誰可以接在誰後面」

LeetCode 2267 解題筆記：狀態是 (r, c, 左括號餘額)；餘額不能是負的，也不能超過剩下的步數；BFS / DP 搜尋這些狀態，走到終點時餘額為 0 就成立

LeetCode 2218 解題筆記：每一堆只能從上面拿，拿 x 個的價值是前綴和；分組背包，dp[j] = 前幾堆總共拿 j 個的最大價值，每一堆枚舉拿幾個