打家劫舍到环形街区：动态规划的状态机思维进阶

动态规划（DP）是算法面试中"性价比"最高的题型之一：它不像图论那样依赖大量模板，也不像脑筋急转弯那样依赖灵感，而是一套可以训练、可以推导的思维范式。从 LeetCode 198（打家劫舍）到 213（环形打家劫舍），再到 337（二叉树打家劫舍），这三道题构成了一条经典的进阶路径，揭示了 DP 从"一维数组"向"状态机"演化的核心逻辑。

一、从线性数组开始：定义状态，而非模拟过程

题目描述（LeetCode 198）：给定一个非负整数数组 nums，相邻房屋不能同时被偷。求能偷到的最大金额。

许多初学者会陷入"偷或不偷"的递归模拟：f(i) = max(f(i-1), f(i-2) + nums[i])。但更本质的思考方式是：状态是什么？ 这里的状态 dp[i] 表示"偷到第 i 间房时的最大金额"。关键在于，这个状态天然蕴含了"第 i 间房是否被偷"的信息——如果偷了第 i 间，第 i-1 间必不能偷；如果不偷，则问题退化为 dp[i-1]。

public int rob(int[] nums) {
    if (nums == null || nums.length == 0) return 0;
    int n = nums.length;
    int[] dp = new int[n + 1];
    dp[1] = nums[0];  // 偷第1间
    for (int i = 2; i <= n; i++) {
        // dp[i]：前i间房的最大值，要么不偷第i间（dp[i-1]），要么偷（dp[i-2]+nums[i-1]）
        dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]);
    }
    return dp[n];
}

关键点：dp[i] 的定义已经隐含了"第 i 间房的状态"，因此转移方程不需要显式区分"偷"与"不偷"——这正是 DP 与回溯的区别：回溯枚举所有选择，DP 用状态压缩选择空间。易踩坑：初始化时 dp[1] = nums[0]，而不是 dp[0] = nums[0]，否则会漏掉第一间房。

时间复杂度 O(n)，空间复杂度 O(n)。但更优的解法是滚动数组，只保留 prev2 和 prev1 两个变量，将空间压至 O(1)。为什么能优化？ 因为转移方程只依赖前两个状态，这是线性 DP 的典型特征。

二、环形街区的本质：破环为链

题目描述（LeetCode 213）：房屋围成一圈，首尾视为相邻。其他条件不变。

面对环形问题，第一反应可能是"增加状态维度"，但更简洁的思路是分类讨论：既然首尾不能同时被偷，那么要么不偷第 0 间（只考虑 nums[1:]），要么不偷最后一间（只考虑 nums[:-1]）。两者取最大即可。

public int rob(int[] nums) {
    if (nums.length == 1) return nums[0];
    // 复用线性解法，分别处理去掉首或尾的数组
    return Math.max(robLinear(Arrays.copyOfRange(nums, 0, nums.length - 1)),
                    robLinear(Arrays.copyOfRange(nums, 1, nums.length)));
}

这里 robLinear 就是第一节的代码。关键点：环形问题的破环点在于"首尾冲突"是唯一新增约束，通过枚举两种不冲突的情况，就退化成两个线性子问题。易踩坑：当数组长度为 1 时，copyOfRange 取首尾子数组都为空，会返回 0，因此必须单独处理。

时间复杂度 O(n)，空间复杂度 O(1)（若线性版本用滚动数组）。这个解法不仅适用于打家劫舍，也适用于任何"首尾相关"的 DP 问题，如环形子数组最大和（LeetCode 918）。

三、从数组到树：状态机思维的爆发

题目描述（LeetCode 337）：房屋呈二叉树结构，直接相连的父子节点不能同时被偷。求最大金额。

此时线性 DP 的 dp[i] 失效，因为状态不再有天然的顺序。核心突破：每个节点需要返回两个状态——robSelf（偷当前节点）和 notRob（不偷当前节点）。这就是状态机思想：每个节点是一个微型状态机，父节点的状态由子节点的状态推导。

public int rob(TreeNode root) {
    int[] result = dfs(root);
    return Math.max(result[0], result[1]);
}

private int[] dfs(TreeNode node) {
    if (node == null) return new int[2];  // [robSelf, notRob]
    int[] left = dfs(node.left);
    int[] right = dfs(node.right);
    // 偷当前节点：子节点只能不偷
    int robSelf = node.val + left[1] + right[1];
    // 不偷当前节点：子节点可以偷或不偷，取各自较大值
    int notRob = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
    return new int[]{robSelf, notRob};
}

关键点：后序遍历保证了子节点状态先于父节点计算。robSelf 和 notRob 构成一个二元状态（用 int[2] 数组承载），父节点的转移方程实际上是"状态组合"，而非简单的数值比较。易踩坑：不能只返回一个值，否则无法表达"当前节点不偷时子节点可偷"的灵活性——这正是状态机比单值 DP 强大的地方。

时间复杂度 O(n)（每个节点访问一次），空间复杂度 O(h)（递归栈深度，h 为树高）。为什么这是自然的延伸？ 从一维数组到树，DP 的"状态"从单一数值演化为数组，但核心逻辑不变：定义清楚状态，再写转移方程。

四、进阶启示：何时用状态机？

三道题展示了 DP 的进化路径：线性 → 环形（破环为链）→ 树形（状态机）。面试中遇到新题，可以按此顺序寻找思路：

• 如果状态含顺序（数组、字符串），优先考虑一维 DP，注意能否滚动数组。
• 如果首尾相关，尝试分类讨论，将环形拆成线性。
• 如果状态含层级（树、图），考虑用状态机（返回数组）或树形 DP。

类似题推荐：LeetCode 309（买卖股票含冷冻期）是典型的状态机 DP，需要定义"持有/不持有/冷冻"三态；LeetCode 152（乘积最大子数组）则需要维护最大和最小两个状态，因为负负得正。这些题的共通点是：单一状态不够用，必须用多个状态表达问题的全貌。

下一步行动建议：完成 198、213、337 后，建议立刻做 309 和 152，并尝试手写状态转移图。DP 的瓶颈不在代码，而在"状态定义"的直觉——这种直觉只能通过刻意练习获得，建议每周固定刷 3-4 道 DP 题，按"线性 → 区间 → 背包 → 状态机 → 树形"的顺序推进。

本文关键词：动态规划、状态机、树形DP、LeetCode 198、LeetCode 337