DP 寫程式不難，難的是式子如何推導，解 DP 題目時，需先定義這三件事：
- State：
dp[i]代表什麼？ - Transition：目前狀態如何由較小的子問題得到？常見思路是考慮「選」或「不選」。
- Base case：最小、最初的狀態是什麼？
vector<int> dp(n,0); // 初始化
dp[0]=1; // base case
for(int i=2; i<=n; i++){
dp[i]=dp[i-1]+dp[i-2]; // transition: 依序從之前的答案更新 dp[i]
}
return dp[n];
基礎與選擇 DP
70. Climbing Stairs
這裡我們把 dp[i] 定義為走到第 i 階的方法數，並且我們可以知道走到 i 階的方法有兩種：從 i-1 走 1 階，或從 i-2 走 2 階，所以可以得知 dp[i] = dp[i-1] + dp[i-2]。
746. Min Cost Climbing Stairs
定義dp[i] 為到達第 i 階的最低花費，可以從前一階或前兩階的花費推算。
遇到相鄰位置不能同時選的限制，可比較「選目前項目」和「跳過目前項目」。
198. House Robber
dp[i]代表從 0~i 間房子能獲得的最大收益，如果不搶第 i 間房子，沿用 dp[i-1] 的答案；如果搶第 i 間房子，表示 i-1 不能搶，所以沿用 dp[i-2] 的答案，再加上第 i 間房子的收益。
213. House Robber II
做兩次dp，第一次從房子 0 到 n-2，第二次從房子 1 到 n-1。
337. House Robber III
樹上相鄰節點不能同時選。每個節點回傳兩個值：選它的最高收益（只能加左右子樹「不選」的結果），以及不選它的最高收益（左右子樹各自取較大值）；根節點取兩者較大值。
740. Delete and Earn
先統計每個數值出現次數，選數值 x 可得 x * count[x] 分；因為選了 x 就不能選 x-1 和 x+1，所以其實和 House Robber 一樣。
45. Jump Game II
這題可以用 DP 或 Greedy 解，DP 定義 dp[i] 為到位置 i 的最少步數，可由所有能跳到 i 的位置轉移。
背包問題
0/1 背包
每個物品最多選一次，一維陣列由大到小更新。
416. Partition Equal Subset Sum
問題先轉成能否從數字中選出總和為 sum / 2 的子集合。令 dp[i] 表示是否能湊出總和 i，考慮每個數字的影響。
494. Target Sum
把數字分成加號集合 P 和減號集合 N，則 sum(P) - sum(N) = target，可把問題轉成找子集合總和 (sum + target) / 2 的方法數。
完全背包
每個物品可以重複選，一維陣列由小到大更新。
322. Coin Change
令 dp[i] 為湊出金額 i 所需的最少硬幣數，，考慮每個硬幣的影響。
518. Coin Change II
令 dp[i] 為湊出金額 i 的組合數。
Grid DP
62. Unique Paths
只能向右或向下，因此到每格的路徑數為上方與左方路徑數之和：dp[r][c] = dp[r-1][c] + dp[r][c-1]。
63. Unique Paths II
遇到障礙格就令 dp[r][c] = 0。
64. Minimum Path Sum
令 dp[r][c] 為走到該格的最低總和。
字串與序列 DP
300. Longest Increasing Subsequence
令 dp[i] 為以 nums[i] 結尾的最長遞增子序列長度；檢查所有 j < i 且 nums[j] < nums[i]，取 dp[j] + 1 的最大值。這個 DP 是 O(n²)，也有 O(n log n) 的二分搜解法。
1143. Longest Common Subsequence
令 dp[i][j] 為兩字串前 i、前 j 個字元的 LCS 長度。若最後字元相同，就從左上狀態＋1；不同則取上面、左邊兩種結果的最大值。
72. Edit Distance
令 dp[i][j] 為把一字串前綴改成另一字串前綴所需的最少操作數。字元相同時沿用左上值；不同時考慮插入/刪除(左/上)、替換(左上)，取三者最小值再加一。
139. Word Break
令 dp[i] 表示字串前 i 個字元能否被字典切分。枚舉任一段起點 j；若 dp[j-1] 為 true 且 s[j..i] 在字典中，則 dp[i] = true。
