Dynamic-Programming

使用單調堆疊解決直方圖中最大矩形面積問題

LeetCode 1696 解題筆記：dp[i] = nums[i] + 前 k 個 dp 的最大值；前 k 個的最大值用單調佇列維護，O(n)

LeetCode 3638 解題筆記：貪心，一段一旦出現比這段最大值小的數就馬上切；因為切之前的那段是非遞減的，最大值就是前一個數

用 ending-here invariant 解 Maximum Subarray

LeetCode 2745 解題筆記：AA 和 BB 必須交替出現，最多用 min(x, y) 對，多的那種還能再多放一個；AB 全部都能接上

LeetCode 473 解題筆記：總和要能被 4 整除；由大到小把每根火柴放進四個邊之一，超過邊長或跟前一個邊長度相同就跳過

LeetCode 435 解題筆記：最少刪幾個 = 總數減掉最多能保留幾個；按右端點排序，貪心保留結束最早的

LeetCode 397 解題筆記：偶數一定除以 2；奇數選 +1 或 -1，用記憶化遞迴；n 很大不能開 n 大小的陣列

LeetCode 396 解題筆記：F(k) 和 F(k - 1) 只差一個公式：F(k) = F(k - 1) + sum - n × 被移到最前面的那個數

LeetCode 337 解題筆記：樹上 DP，每個節點回傳（搶它、不搶它）的最大值；不是一層一層交錯搶

LeetCode 313 解題筆記：LC 264 的推廣，每個質數一個指針；用 heap 的話要避免同一個數被推進去很多次

LeetCode 338 解題筆記：dp[i] = dp[i » 1] + (i & 1)，或 dp[i] = dp[i - 最高位的 2 的次方] + 1