以最長遞增子序列為例
🎯 首先明確目標
以最長上升子序列（LIS）為例，假設輸入是：
nums := []int{10, 9, 2, 5, 3, 7, 101, 18}
我們定義：
dp[i]：以 nums[i] 為結尾的最長上升子序列長度
目標：求 dp[i] 的最大值。
🔍 雙重 for 的意義是什么？
for i := 1; i < n; i++ {for j := 0; j < i; j++ {if nums[j] < nums[i] {dp[i] = max(dp[i], dp[j] + 1)}}
}
這里我們來解釋：
? 第一層循環：從左到右遍歷每一個位置 i
我們要計算：以 nums[i] 結尾的“最長上升子序列”是多少？
? 第二層循環：查看所有在 i 之前的數 j
對于每一個前面的數 nums[j]，判斷：
它是否可以作為
nums[i]的前一個元素？
也就是判斷nums[j] < nums[i]。
如果是，就說明：
如果我以
j為結尾的子序列有長度dp[j]，
那么我在它后面加上nums[i]，就可以構成一個更長的上升序列，長度是dp[j] + 1。
于是我們嘗試更新 dp[i]：
dp[i] = max(dp[i], dp[j] + 1)
🔁 用人話解釋一遍：
“我想知道
nums[i]能不能接在某個前面的上升序列后面，
如果能，那我就更新一下它作為結尾時，能組成多長的子序列。”
🧠 一個具體例子（帶注釋）
nums := []int{10, 9, 2, 5, 3, 7}初始化 dp := []int{1, 1, 1, 1, 1, 1} // 每個位置起碼是自己i = 3, nums[3] = 5j = 0, nums[0] = 10 -> 跳過j = 1, nums[1] = 9 -> 跳過j = 2, nums[2] = 2 -> 2 < 5 -> 更新 dp[3] = max(1, dp[2] + 1) = 2i = 4, nums[4] = 3j = 0 -> 10 > 3 -> 跳過j = 1 -> 9 > 3 -> 跳過j = 2 -> 2 < 3 -> dp[4] = max(1, dp[2]+1) = 2j = 3 -> 5 > 3 -> 跳過i = 5, nums[5] = 7j = 0 -> 10 > 7 -> 跳過j = 1 -> 9 > 7 -> 跳過j = 2 -> 2 < 7 -> dp[5] = max(1, 1+1) = 2j = 3 -> 5 < 7 -> dp[5] = max(2, 2+1) = 3j = 4 -> 3 < 7 -> dp[5] = max(3, 2+1) = 3
🧩 為什么不能只用一個循環？
因為我們求的是：
“在前面所有滿足條件的數里，找一個最優的情況來更新當前的狀態”。
只有看完所有的 j < i 才能找到最優的更新路徑，所以必須有一個內層循環來“掃描過去”。
? 總結記憶方法：
-
i是當前狀態 -
j是過去狀態 -
if 條件成立，說明可以從過去j走到現在i -
dp[i] = max(dp[i], dp[j]+1)就是取過去所有能轉移過來的路徑中最優的那一條
for i := 1; i < n; i++ {for j := 0; j < i; j++ {// 某種條件成立// dp[i] = max(dp[i], dp[j] + ...)}
}
這類“雙重 for + 狀態轉移”的寫法，在一類特定的動態規劃問題中非常經典和高頻。這類問題一般具有以下特征：
? 典型問題特征
-
子問題具有前后關系（i/j 結構）
-
當前狀態
i要依賴過去某些狀態j < i -
類似“前綴分析”
-
-
具有單調性約束
-
如
nums[j] < nums[i]、end[j] <= start[i]等條件
-
-
求解最大/最小值
-
求“最長”、“最大收益”、“最多區間”、“最優策略”
-
? 高頻問題示例
| 問題類型 | 描述 | dp含義 | 轉移條件 |
|---|---|---|---|
| 最長上升子序列 (LIS) | 找遞增的最大長度 | dp[i]：以 i 結尾的最長長度 | nums[j] < nums[i] |
| 最長不下降子序列 | 可以等于也遞增 | dp[i] | nums[j] <= nums[i] |
| 最長擺動子序列 | 上下起伏交替 | up[i], down[i] | 比較大小后轉移 |
| 最大不重疊區間數 | 按 end 排序后貪心/DP | dp[i]：前 i 個的最大區間數 | end[j] <= start[i] |
| 最大信封嵌套數（俄羅斯套娃） | 求最多可嵌套信封數 | 對寬升高做 LIS | w[j] < w[i] && h[j] < h[i] |
| 打家劫舍變形 | 不偷相鄰的 | dp[i]：前 i 個最大金額 | dp[i] = max(dp[i-1], dp[i-2]+nums[i]) |
| 最大連續子數組積 | 需要 max 和 min | max[i], min[i] 同時維護 | 根據乘積正負轉移 |
? 模板結構（可抽象成函數）
for i := 1; i < n; i++ {for j := 0; j < i; j++ {if 滿足條件(j, i) {dp[i] = max(dp[i], dp[j] + 某個值)}}
}
? 小技巧：可以加上前向指針以恢復路徑
prev := make([]int, n) // 記錄轉移路徑
for i := range prev {prev[i] = -1
}
...
if dp[j] + 1 > dp[i] {dp[i] = dp[j] + 1prev[i] = j
}
如果你以后看到類似“最XXX的子序列”“最XXX的不重疊區間”，只要是“i依賴j”型的問題，幾乎都可以優先嘗試這個模板。
