瀏覽標記為 dynamic programming 的 4 篇筆記。

#dynamic programming

LeetCode 198：打家劫舍，用兩個狀態處理搶與不搶

記錄我的 House Robber 解法，拆解 p1、p2 為什麼可行，再改成狀態定義更清楚的 O(n) 時間、O(1) 額外空間版本。

記錄我的 Climbing Stairs 解題過程，從排列組合誤區、指數時間遞迴，走到 O(n) 時間與 O(1) 額外空間的 rolling state。

記錄我的 Maximum Product Subarray 解題過程，從正負號分支改成 O(n) 的最大與最小雙狀態，並用反例、不變量及暴力比對說明正確性。

記錄我的 Maximum Subarray 解題過程，從 O(n²) 向左掃描改成 O(n)，解釋 endingHere 與 best 的差別、全負數邊界與可執行測試。