线性动态规划 (1D DP)：掌握一维动态规划

什么是线性动态规划？

线性动态规划（一维DP） 是最基础的DP模式，状态依赖于单个序列中的前面元素。DP表是一个一维数组，其中 dp[i] 表示涉及从索引0到i的元素的子问题的最优解。

核心特征

1. 一维状态: dp[i] 表示位置 i 处的某个最优值
2. 顺序依赖: 每个状态依赖于一个或多个前面的状态
3. 线性遍历: 我们只需遍历数组一次（或常数次）
4. 常见时间复杂度: $O(n)$ 到 $O(n^2)$

常见线性DP模式

模式	状态定义	转移方程	示例
选择或跳过	dp[i] = 考虑0..i的最优值	dp[i] = max(dp[i-1], dp[i-2] + val[i])	打家劫舍
扩展或重启	dp[i] = 以i结尾的最优值	dp[i] = max(dp[i-1] + val[i], val[i])	最大子数组
计数	dp[i] = 到达状态i的方法数	dp[i] = dp[i-1] + dp[i-2]	爬楼梯
有界搜索	dp[i] = 前缀i的最优值	dp[i] = min(dp[j] + cost)	单词拆分

---

”选择或跳过”模式

这是最常见的线性DP模式之一。在每个位置，你决定是”选择”当前元素（这会影响你之前能选择什么）还是”跳过”它。

直观理解

打家劫舍：不能抢相邻的房屋

房屋:    [2]  [7]  [9]  [3]  [1]
索引:     0    1    2    3    4

在每个房屋，你有2个选择：
  - 抢：加上它的价值 + 2个房屋前的最优解
  - 跳过：取前一个房屋的最优解

dp[0] = 2         (抢房屋0)
dp[1] = max(7, 2) = 7    (跳过0抢1 或 抢0跳过1)
dp[2] = max(7, 2+9) = 11 (跳过2 或 抢0和2)
dp[3] = max(11, 7+3) = 11 (跳过3 或 抢1和3)
dp[4] = max(11, 11+1) = 12 (跳过4 或 抢0,2,4)

---

交互式可视化：打家劫舍

Loading visualization...

---

问题一：打家劫舍 (LC 198)

问题：沿街抢劫房屋，不能抢相邻的两间。求最大金额。

状态定义: dp[i] = 抢劫房屋0到i的最大金额

转移方程:

dp[i] = max(
    dp[i-1],           // 跳过当前房屋
    dp[i-2] + nums[i]  // 抢当前房屋
)

关键洞察: 这是典型的”选择或跳过”模式，有约束（不能选择相邻的）。

JavaPythonJavaScript

Loading...

空间优化

由于 dp[i] 只依赖于 dp[i-1] 和 dp[i-2]，我们可以将空间从 $O(n)$ 降到 $O(1)$：

prev2 ← prev1 ← current

---

“扩展或重启”模式

在每个位置，决定是扩展前一个最优解还是从当前位置重新开始。

直观理解：Kadane算法

最大子数组：找到和最大的连续子数组

数组:  [-2]  [1]  [-3]  [4]  [-1]  [2]  [1]  [-5]  [4]
索引:    0    1     2    3     4    5    6     7    8

在每个位置：
  - 扩展：把当前值加到前一个"以此结尾的最优"
  - 重启：从当前元素重新开始子数组

dp[0] = -2  (唯一选择)
dp[1] = max(1, -2+1) = 1      (重启更好！)
dp[2] = max(-3, 1-3) = -2     (扩展更好)
dp[3] = max(4, -2+4) = 4      (重启更好！)
dp[4] = max(-1, 4-1) = 3      (扩展)
dp[5] = max(2, 3+2) = 5       (扩展)
dp[6] = max(1, 5+1) = 6       (扩展)  ← 全局最大值！

---

交互式可视化：最大子数组

Loading visualization...

---

问题二：最大子数组和 (LC 53)

问题：找到和最大的连续子数组。

状态定义: dp[i] = 以索引i结尾的最大子数组和

转移方程:

dp[i] = max(
    nums[i],              // 开始新子数组
    dp[i-1] + nums[i]     // 扩展前一个子数组
)

关键洞察: 如果 dp[i-1] 是负数，重新开始总是更好！

JavaPythonJavaScript

Loading...

为什么这样有效

Kadane算法的关键洞察：

• 如果以 i-1 结尾的最优子数组和是正的，扩展它只会有帮助
• 如果是负的，我们最好重新开始

---

”无界背包”模式

当你可以多次使用物品来达到目标时，状态表示目标值，我们在每一步遍历所有物品。

直观理解：零钱兑换

硬币: [1, 2, 5], 金额: 11

dp[i] = 凑成金额i所需的最少硬币数
dp[0] = 0 (基础情况)

对于从1到11的每个金额：
  尝试每个硬币，取最小值

金额 1: 硬币1 → dp[0]+1=1          → dp[1]=1
金额 2: 硬币1 → dp[1]+1=2
        硬币2 → dp[0]+1=1          → dp[2]=1
金额 5: 硬币1 → dp[4]+1=3
        硬币2 → dp[3]+1=3
        硬币5 → dp[0]+1=1          → dp[5]=1
金额 11: 硬币1 → dp[10]+1=4
         硬币2 → dp[9]+1=4
         硬币5 → dp[6]+1=3         → dp[11]=3

---

交互式可视化：零钱兑换

Loading visualization...

---

问题三：零钱兑换 (LC 322)

问题：找到凑成金额所需的最少硬币数。硬币数量无限。

状态定义: dp[i] = 凑成金额i所需的最少硬币数

转移方程:

dp[i] = min(dp[i - coin] + 1) 对于每个 coin <= i

JavaPythonJavaScript

Loading...

相关问题

• LC 518: 零钱兑换 II - 计算组合数
• LC 279: 完全平方数 - 相同模式，用平方数

---

问题四：解码方法 (LC 91)

问题：计算解码数字字符串的方法数（1→A, 2→B, …, 26→Z）。

状态定义: dp[i] = 解码s[0..i-1]的方法数

转移方程:

dp[i] = 0
如果 s[i-1] 是有效单数字 (1-9):  dp[i] += dp[i-1]
如果 s[i-2..i-1] 是有效双数字 (10-26): dp[i] += dp[i-2]

关键洞察: 类似爬楼梯，但有条件转移。

JavaPythonJavaScript

Loading...

边界情况

• 前导零: “0” 或 “00” → 无效
• 中间有零: “10” 有效, “01” 无效
• 数字 > 26: “27” 只能解码为 “2”,“7”

---

问题五：最长递增子序列 (LC 300)

问题：找到最长严格递增子序列的长度。

DP方法 - $O(n^2)$

状态定义: dp[i] = 以索引i结尾的LIS长度

转移方程:

dp[i] = max(dp[j] + 1) 对于所有 j < i 且 nums[j] < nums[i]

二分查找方法 - $O(n \log n)$

维护一个 tails 数组，其中 tails[i] 是长度为i+1的LIS的最小尾部元素。

nums = [10, 9, 2, 5, 3, 7, 101, 18]

处理每个数字：
10: tails = [10]
 9: tails = [9]         (用更小的9替换10)
 2: tails = [2]         (用更小的2替换9)
 5: tails = [2, 5]      (扩展)
 3: tails = [2, 3]      (用更小的3替换5)
 7: tails = [2, 3, 7]   (扩展)
101: tails = [2, 3, 7, 101]  (扩展)
18: tails = [2, 3, 7, 18]    (替换101)

答案 = len(tails) = 4

JavaPythonJavaScript

Loading...

---

问题六：单词拆分 (LC 139)

问题：字符串能否被拆分成字典中的单词？

状态定义: dp[i] = s[0..i-1]能否被拆分

转移方程:

dp[i] = true 如果存在 j < i 使得:
    dp[j] 为 true 且 s[j..i-1] 在字典中

JavaPythonJavaScript

Loading...

---

空间优化技巧

大多数线性DP可以从 $O(n)$ 优化到 $O(1)$ 空间：

当 dp[i] 依赖于 dp[i-1] 和 dp[i-2]

// 优化前: O(n) 空间
int[] dp = new int[n];
dp[0] = ...; dp[1] = ...;
for (int i = 2; i < n; i++) {
    dp[i] = f(dp[i-1], dp[i-2]);
}
return dp[n-1];

// 优化后: O(1) 空间
int prev2 = ..., prev1 = ...;
for (int i = 2; i < n; i++) {
    int curr = f(prev1, prev2);
    prev2 = prev1;
    prev1 = curr;
}
return prev1;

当只需要 dp[i-1]

// 只用一个变量！
int prev = base_value;
for (int i = 1; i < n; i++) {
    prev = f(prev, nums[i]);
}
return prev;

---

常见模式总结

问题类型	状态	转移	时间	空间
打家劫舍	0..i的最大金额	max(跳过, 选择)	O(n)	O(1)
最大子数组	以i结尾的最大和	max(扩展, 重启)	O(n)	O(1)
爬楼梯	到台阶i的方法数	dp[i-1] + dp[i-2]	O(n)	O(1)
零钱兑换	金额i的最少硬币	min(dp[i-coin]+1)	O(n*m)	O(n)
解码方法	解码0..i的方法数	条件求和	O(n)	O(1)
单词拆分	0..i能否拆分	有效拆分的OR	O(n²*m)	O(n)
LIS	以i结尾的LIS	max(dp[j]+1)	O(n²)	O(n)

---

面试技巧

如何识别线性DP

1. “求最大/最小…” 有约束 → 选择或跳过
2. “计算方法数…” → 子问题相加
3. “是否可能…” → 布尔DP用OR
4. “连续子数组” → 扩展或重启模式

常见错误

1. 忘记基础情况: 总是处理n=0, n=1
2. 迭代方向错误: 确保依赖项先计算
3. 差一错误: 明确dp[i]是”前i个”还是”以i结尾”
4. 没考虑负数: 影响重启决策

面试官可能问的优化问题

1. “能优化空间吗？” → 滚动数组或变量
2. “能比O(n²)更好吗？” → 二分查找（如LIS）
3. “如果数组很大怎么办？” → 考虑流式处理

---

练习题目

简单

• LC 70: 爬楼梯
• LC 746: 使用最小花费爬楼梯

中等

• LC 198: 打家劫舍
• LC 213: 打家劫舍 II（环形）
• LC 53: 最大子数组和
• LC 322: 零钱兑换
• LC 91: 解码方法
• LC 300: 最长递增子序列
• LC 139: 单词拆分
• LC 152: 乘积最大子数组

困难

• LC 140: 单词拆分 II
• LC 188: 买卖股票的最佳时机 IV

---

总结

线性DP关键要点：

1. 状态是一维的: dp[i] 表示位置i处/之前的最优值

2. 三种主要模式:

   • 选择或跳过: dp[i] = max(dp[i-1], dp[i-2] + val[i])
   • 扩展或重启: dp[i] = max(dp[i-1] + val[i], val[i])
   • 有界搜索: dp[i] = optimal(dp[j] + cost) 对于有效的j

3. 空间优化: 大多数1D DP可以用滚动变量达到O(1)空间

4. 时间复杂度: 通常是O(n)到O(n²)，有时可以优化到O(n log n)

掌握这些模式，你就能解决面试中80%的线性DP问题！