02 一维线性DP：「选或不选」框架与打家劫舍系列

一维线性 DP：「选或不选」框架与打家劫舍系列

摘要

一维线性 DP 是动态规划中形式最简单、应用最广泛的一类问题。其核心模式只有一个——对每个元素做二选一决策：选它，或者不选它。本文以打家劫舍系列（House Robber I/II）为主线，深入剖析”相邻约束”下的选与不选框架；再通过 Delete and Earn 展示”问题转化”这一 DP 解题思想——同一个框架，套在不同问题外皮下，化腐朽为神奇。掌握本文内容，你将能识别并秒解面试中 70% 以上的线性 DP 题目。

---

第 1 章 线性 DP 的本质：对序列的逐元素决策

1.1 什么是线性 DP

所谓”线性 DP”，是指状态只有一个维度（或主维度是序列长度），且状态转移只依赖于序列的相邻几个状态的 DP 类型。最典型的形式是：

$dp[i]=f(dp[i-1],dp[i-2],\dots ,dp[i-k])$

其中 $k$ 是一个较小的常数（通常为 1 或 2）。爬楼梯、斐波那契、打家劫舍都属于这个范畴。

1.2 「选或不选」框架

线性 DP 中最常见的决策模式是”对每个元素，选它或者不选它”。这个框架有几个关键特征：

• 决策是二元的：选 vs 不选
• 选与不选有约束：通常不能连续选（打家劫舍），或者必须按某种规则选
• 求的是所有合法选法中的最优解（最大值、最小值或方案数）

当看到题目中出现”不能相邻选”、“隔 k 个才能选”等约束时，脑子里应该立即跳出这个框架。

1.3 为什么「选或不选」能统一这么多问题

从信息论的角度看，对一个长度为 $n$ 的序列，每个元素有 2 种选择，共有 $2^n$ 种可能的选法。暴力枚举是指数级的。

「选或不选」DP 的精髓在于：利用最优子结构，把 $2^n$ 种枚举压缩成 $O(n)$ 的递推。具体来说，dp[i] 存储的是”考虑了前 $i$ 个元素之后的最优解”，而这个最优解只取决于 dp[i-1] 和 dp[i-2]（因为相邻约束最多看两步），与具体如何到达这个状态的路径无关。

这种”状态与路径无关”的性质，就是最优子结构的体现。

---

第 2 章 LeetCode 198：打家劫舍（完整版）

2.1 题目回顾与深度分析

LeetCode 198 - House Robber（中等）

输入: nums = [2, 7, 3, 1, 4, 2]
输出: 11
解释: 偷 nums[1]=7 和 nums[4]=4，共 11。

输入: nums = [2, 1, 1, 2]
输出: 4
解释: 偷 nums[0]=2 和 nums[3]=2，共 4。

2.2 贪心为什么不行

直觉上可能会想：每次选局部最大值，跳过它的邻居，再选下一个局部最大值，这样不就是贪心吗？

看这个例子：[2, 1, 1, 2]

• 贪心：选 nums[0]=2，跳过 nums[1]=1，选 nums[2]=1（它是下一个局部最大），结果 = 3
• 最优：选 nums[0]=2 和 nums[3]=2，结果 = 4

贪心失败。原因是：局部最优不等于全局最优，选了某个”局部大”的元素，可能让你错过两个”局部小”但合起来更大的元素组合。

生产避坑：贪心 vs DP 的边界

贪心算法在每一步只看”当前最优”，不回溯。只有当”局部最优”能推出”全局最优”时，贪心才正确（比如活动选择问题、最小生成树）。打家劫舍中，“选当前房屋”的决策会影响后续多个选择，不满足贪心的前提，必须用 DP 枚举所有可能。

2.3 四步法完整推导

第一步：识别。求最大金额 → 最优化问题。子问题 rob(i) 和 rob(i-2) 等在递归中反复出现 → 重叠子问题。✅

第二步：定义状态。

dp[i] = 考虑了 nums[0..i]（前 i+1 间房屋），能偷到的最大金额。

注意”考虑了”不等于”必须偷了”。dp[i] 是综合考虑前 i+1 间房后的全局最优，可能包含也可能不包含第 i 间房。

第三步：转移方程。

对第 i 间房，两个选择：

1. 不偷第 i 间：最优金额是 dp[i-1]（前 i 间的最优解，第 i 间不贡献任何金额）
2. 偷第 i 间：由于相邻约束，第 i-1 间不能偷，最优金额是 dp[i-2] + nums[i]

$dp[i]=\max (dp[i-1],dp[i-2]+nums[i])$

第四步：初始化 + 遍历。

• dp[0] = nums[0]（只有一间房，偷它）
• dp[1] = max(nums[0], nums[1])（两间房，选大的偷）
• 正序遍历 i 从 2 到 n-1

2.4 完整实现

public int rob(int[] nums) {
    int n = nums.length;
    if (n == 1) return nums[0];
    if (n == 2) return Math.max(nums[0], nums[1]);
 
    int[] dp = new int[n];
    dp[0] = nums[0];
    dp[1] = Math.max(nums[0], nums[1]);
 
    for (int i = 2; i < n; i++) {
        // 对第 i 间房：偷 vs 不偷，取最大值
        dp[i] = Math.max(dp[i - 1],           // 不偷第 i 间，沿用前 i 间的最优解
                         dp[i - 2] + nums[i]); // 偷第 i 间，加上跳过 i-1 后的最优解
    }
    return dp[n - 1];
}

空间压缩到 $O(1)$：

public int rob(int[] nums) {
    int n = nums.length;
    if (n == 1) return nums[0];
 
    int prev2 = nums[0];                          // dp[i-2]
    int prev1 = Math.max(nums[0], nums[1]);       // dp[i-1]
 
    for (int i = 2; i < n; i++) {
        int curr = Math.max(prev1, prev2 + nums[i]);
        prev2 = prev1;
        prev1 = curr;
    }
    return prev1;
}

2.5 边界情况详解

情况	处理方式	原因
n = 1	直接返回 nums[0]	只有一间房，必须偷
n = 2	返回 max(nums[0], nums[1])	两间房相邻，只能偷一间
n >= 3	正常 DP	至少有 3 间时，dp[i-2] 总是合法的

---

第 3 章 LeetCode 213：打家劫舍 II（环形数组）

3.1 问题升级：房屋变成环形

LeetCode 213 - House Robber II（中等）

所有房屋排成一个圆圈，第一间和最后一间相邻。其他规则与 House Robber I 相同。

输入: nums = [2, 3, 2]
输出: 3
解释: 不能偷 nums[0]=2 和 nums[2]=2（它们相邻），最多只能偷 nums[1]=3。

输入: nums = [1, 2, 3, 1]
输出: 4
解释: 偷 nums[0]=1 和 nums[2]=3，合计 4。

3.2 环形约束的关键矛盾

House Robber I 的 DP 假设第一间和最后一间不相邻——可以同时偷。但环形结构打破了这个假设：如果偷了 nums[0]，就不能偷 nums[n-1]；如果偷了 nums[n-1]，就不能偷 nums[0]。

直接套用 House Robber I 的 DP 不行，因为转移方程 dp[i] = max(dp[i-1], dp[i-2] + nums[i]) 没有处理 nums[0] 和 nums[n-1] 的互斥关系。

3.3 化环为链：核心思路

关键观察：不管最优解如何，nums[0] 和 nums[n-1] 不可能同时被选（因为它们相邻）。换句话说，最优解只有两种情况：

1. 不选 nums[n-1]：考虑的范围是 nums[0..n-2]（去掉最后一间）
2. 不选 nums[0]：考虑的范围是 nums[1..n-1]（去掉第一间）

对每种情况分别跑一次 House Robber I 的 DP，取两者的最大值，即为答案。

核心概念：化环为链

处理环形约束的通用技巧：枚举”打破环”的位置，把环形问题转化为若干线性问题。本题中，通过枚举”不选第一间”或”不选最后一间”，将环形数组转化为两个线性数组，各跑一次线性 DP，取最大值。 这个技巧在图的环形处理、环形链表等问题中也有广泛应用。

3.4 实现

public int rob(int[] nums) {
    int n = nums.length;
    if (n == 1) return nums[0];
    if (n == 2) return Math.max(nums[0], nums[1]);
 
    // 情况 1：考虑 nums[0..n-2]（不含最后一间）
    int case1 = robRange(nums, 0, n - 2);
    // 情况 2：考虑 nums[1..n-1]（不含第一间）
    int case2 = robRange(nums, 1, n - 1);
 
    return Math.max(case1, case2);
}
 
// 对 nums[start..end] 跑标准的 House Robber I DP
private int robRange(int[] nums, int start, int end) {
    if (start == end) return nums[start];
 
    int prev2 = nums[start];
    int prev1 = Math.max(nums[start], nums[start + 1]);
 
    for (int i = start + 2; i <= end; i++) {
        int curr = Math.max(prev1, prev2 + nums[i]);
        prev2 = prev1;
        prev1 = curr;
    }
    return prev1;
}

3.5 正确性证明

为什么对两个区间各跑一次 DP 就够了？

充分性：最优解中，nums[0] 和 nums[n-1] 至少有一个不被选。

• 如果 nums[0] 不被选：最优解完全包含在 nums[1..n-1] 中，robRange(nums, 1, n-1) 的结果包含这个最优解
• 如果 nums[n-1] 不被选：最优解完全包含在 nums[0..n-2] 中，robRange(nums, 0, n-2) 的结果包含这个最优解

因此，两次 DP 中至少有一次能给出全局最优解，取 max 即可。

必要性（为什么不需要更多情况）：两种情况已经覆盖了所有可能，没有第三种情况需要枚举。

---

第 4 章 LeetCode 337：打家劫舍 III（树形变体）

4.1 从线性到树形

LeetCode 337 - House Robber III（中等）

房屋组成二叉树（而不是直线），相邻房屋是树中的父子节点。从二叉树根节点出发，不能同时偷父子节点，求最大金额。

这道题不再是线性 DP，而是树形DP，放在本文中是为了完整呈现打家劫舍系列的演进，正式讲解放在树形DP与状态压缩DP一文。

简要思路：对每个节点 node，定义两个状态：

• dp[node][0]：不偷 node 时，以 node 为根的子树能偷到的最大金额
• dp[node][1]：偷 node 时，以 node 为根的子树能偷到的最大金额

递推关系：

• dp[node][1] = node.val + dp[left][0] + dp[right][0]（偷了 node，子节点都不能偷）
• dp[node][0] = max(dp[left][0], dp[left][1]) + max(dp[right][0], dp[right][1])（不偷 node，子节点可选）

---

第 5 章 LeetCode 740：删除并获得点数

5.1 题目

LeetCode 740 - Delete and Earn（中等）

给你一个整数数组 nums，你可以对它进行一些操作。

每次操作中，选择任意一个 nums[i]，删除它并获得 nums[i] 的点数。之后，你必须删除所有等于 nums[i] - 1 和 nums[i] + 1 的元素。

返回你能通过这些操作获得的最大点数。

输入: nums = [3, 4, 2]
输出: 6
解释: 删除 4，获得 4 点数，但 3 也被删除了。之后删除 2，获得 2 点数。共 6 点。

输入: nums = [2, 2, 3, 3, 3, 4]
输出: 9
解释: 删除 3 并获得 3 点数，再删 3 获得 3 点数，再删 3 获得 3 点数，共 9 点。
     （删除任何一个 3 会导致所有 2 和 4 被删除，但 9 > 8 = 2+2+4。）

5.2 问题转化：从”删除”到”打家劫舍”

这道题的关键在于识别到一个关键特征：当你选择了数值 x，所有等于 x-1 和 x+1 的元素都会被删除。

这意味着：一旦你决定”要取数值 x”，你就自动放弃了所有数值为 x-1 和 x+1 的元素。

如果我们把数组中所有数值归类，对每个数值 v，计算”如果选了 v，总共能获得多少点数”：

$\text{gain}[v]=v\times \text{count}(v)$

其中 count(v) 是 v 在数组中出现的次数。

现在问题变成了：从 gain[0], gain[1], ..., gain[max_val] 这个序列中，选取若干元素使总和最大，但不能选相邻的元素（选了 gain[x] 就不能选 gain[x-1] 和 gain[x+1]）。

这正是打家劫舍 I！

核心概念：问题转化

Delete and Earn 表面是”删除操作”的题，本质是打家劫舍的变形。识别这种等价变换是解 DP 题的核心能力之一： 原问题 → 建模为等价的更简单问题 → 套用已知 DP 框架 这种”先转化，后套框架”的思路，是面试中解新题的核心方法。

5.3 完整实现

public int deleteAndEarn(int[] nums) {
    // 第一步：统计每个数值的出现次数，并计算 gain 数组
    int maxVal = 0;
    for (int num : nums) maxVal = Math.max(maxVal, num);
 
    int[] gain = new int[maxVal + 1];
    for (int num : nums) {
        gain[num] += num;  // 选择数值 num，每次出现贡献 num 点数
    }
 
    // 第二步：对 gain 数组跑打家劫舍 I 的 DP
    // gain[v] 和 gain[v+1] 不能同时选（因为 v 和 v+1 相邻）
    if (maxVal == 0) return 0;
    if (maxVal == 1) return gain[1];
 
    int prev2 = gain[0];
    int prev1 = Math.max(gain[0], gain[1]);
 
    for (int i = 2; i <= maxVal; i++) {
        int curr = Math.max(prev1, prev2 + gain[i]);
        prev2 = prev1;
        prev1 = curr;
    }
    return prev1;
}

时间复杂度：$O(n+\text{maxVal})$，其中 $n$ 是数组长度，maxVal 是数组最大值。空间复杂度 $O(\text{maxVal})$。

5.4 边界与特殊情况

情况一：nums = [1]

gain = [0, 1]，打家劫舍 I 返回 1。正确。

情况二：nums = [1, 1, 1, 2, 4]

gain = [0, 3, 2, 0, 4]（选 1 得 3 点，选 2 得 2 点，选 4 得 4 点）

打家劫舍：

• dp[0] = 0
• dp[1] = 3
• dp[2] = max(3, 0+2) = 3
• dp[3] = max(3, 3+0) = 3
• dp[4] = max(3, 3+4) = 7

结果 7：选 1（得 3 点）和选 4（得 4 点）。✅

情况三：所有元素相同，如 nums = [3, 3, 3, 3]

gain[3] = 12，其他都是 0。打家劫舍返回 12。

---

第 6 章 线性 DP 模式总结

6.1 「选或不选」的核心转移方程

绝大多数一维线性 DP 题的转移方程都是以下两种形式之一：

形式 A：相邻约束（打家劫舍类）

$dp[i]=\max (dp[i-1],dp[i-2]+\text{val}[i])$

特征：不能连续选，选了第 $i$ 个元素就必须跳过第 $i-1$ 个。

形式 B：前缀最优（爬楼梯类）

$dp[i]=\max (dp[i-1]+\text{cost},dp[i-2]+\text{cost})$

特征：每个位置只依赖前几个位置的最优解，当前选择对后续没有”禁止”效果。

6.2 线性 DP 的两种状态定义风格

风格 1：dp[i] = 考虑了前 i 个元素的全局最优

优点：自然，初始化和遍历直观 缺点：无法区分”最后一个元素是否被选”

风格 2：dp[i][0/1] = 第 i 个元素未被选/被选时的最优

优点：能显式区分最后一个元素的选择状态 缺点：状态多了一维，代码稍复杂

对打家劫舍 I，风格 1 更简洁；但对打家劫舍 III（树形 DP），风格 2 是必须的——因为需要区分”根节点被选”和”根节点未被选”的两种情况，才能正确合并子树的状态。

6.3 线性 DP 与「先转化再套框架」

Delete and Earn 的解题路径是：

原问题（删除操作）
   ↓ 建模
每个数值 v 的总收益 = v × count(v)
   ↓ 识别等价关系
选了 v 就不能选 v±1 = 不能选相邻元素
   ↓ 套框架
打家劫舍 I 的 DP

这个”先建模，识别等价，再套框架”的思路是面试高频的解题路径。练习这种思路的方法：每解完一道题，问自己”这道题和哪道已知题目是等价的？“

6.4 高频面试题型汇总

题目	类型	核心技巧
LeetCode 70 爬楼梯	线性 DP	dp[i] = dp[i-1] + dp[i-2]
LeetCode 198 打家劫舍	选或不选	相邻约束，dp[i] = max(dp[i-1], dp[i-2]+val)
LeetCode 213 打家劫舍 II	环形转线性	化环为链，两次线性 DP
LeetCode 337 打家劫舍 III	树形 DP	每个节点 2 个状态，DFS 后序
LeetCode 740 删除并获得	问题转化	建模为打家劫舍 I
LeetCode 746 最小代价爬楼梯	线性 DP	选择出发点，dp[i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2])

---

第 7 章 深入思考：状态压缩的本质

7.1 为什么可以把 dp 数组压缩到两个变量

观察打家劫舍的转移方程：dp[i] = max(dp[i-1], dp[i-2] + nums[i])

计算 dp[i] 只需要 dp[i-1] 和 dp[i-2]。计算 dp[i+1] 只需要 dp[i] 和 dp[i-1]……

因此，在正序遍历过程中，只需要保留”最近两个 dp 值”，就能不断推进计算。dp[0], dp[1], ..., dp[i-3] 在计算 dp[i] 时已经无用，可以释放。

这种优化叫做滚动数组（Rolling Array）——让数组”滚动”前进，只保留当前计算所需的窗口大小的历史数据。

7.2 滚动数组的适用条件

滚动数组只有在转移只依赖固定个数的历史状态时才能应用。例如：

• dp[i] 依赖 dp[i-1] 和 dp[i-2] → 可以用两个变量替代整个数组（本文的情况）
• dp[i][j] 依赖 dp[i-1][j]、dp[i-1][j-1]、dp[i-1][j+1] → 可以用两行（或一行）替代整个二维数组（背包问题的情况）
• dp[i][j] 依赖 dp[k][j-1] for all k < i → 不能简单滚动，需要前缀最大值等辅助结构

设计哲学：空间优化的顺序

在面试中，建议先写出完整的 dp 数组版本，确认正确后再优化空间。 优化顺序：dp[n] 数组 → 两个变量（如果只依赖 1-2 步历史） 不要在还没确认转移方程正确时就急着压缩空间，那样出了 bug 更难排查。

---

第 8 章 拓展练习

完成本文之后，建议尝试以下题目巩固「选或不选」框架：

8.1 LeetCode 1277：统计全为 1 的正方形子矩阵

从一维延伸到二维，但核心仍是”以每个点为右下角，最大正方形是多少”的选或不选推广。

8.2 LeetCode 256：粉刷房子（Pay-wall 题，变体在 1473）

每间房可以涂三种颜色之一，相邻房屋不能涂同一颜色，求最小费用。

状态需要增加一维：dp[i][color] = 第 i 间房涂 color 颜色时的最小总费用。

转移：dp[i][0] = nums[i][0] + min(dp[i-1][1], dp[i-1][2])（涂颜色 0，上一间必须涂 1 或 2）。

8.3 LeetCode 801：使序列递增的最小交换次数

每次操作可以交换 A[i] 和 B[i]，使得 A 和 B 都严格递增的最小交换次数。

状态：dp[i][0/1] = 位置 i 不换/换时的最小操作数。这是需要两个状态才能正确表达”当前位置是否交换”的典型案例。

---

小结

本文通过打家劫舍系列和 Delete and Earn，深入讲解了一维线性 DP 的「选或不选」框架：

1. House Robber I：标准的相邻约束选/不选，转移方程 dp[i] = max(dp[i-1], dp[i-2]+val[i])，空间可压缩到 $O(1)$
2. House Robber II：环形约束化环为链，两次线性 DP 取最大值
3. Delete and Earn：问题建模转化，把”删除操作约束”等价为”相邻约束”，复用打家劫舍框架

下一篇背包问题深度解析：0-1背包、完全背包与空间压缩将把”选或不选”框架从一维推广到二维——每个物品选或不选，且每次选择都会消耗”容量”，这正是背包问题的核心。