打家劫舍：动态规划思维的完美练习场

还记得我们在爬楼梯那道题中初识动态规划的优雅吗？今天让我们通过 LeetCode 198 "打家劫舍"，进一步深入理解动态规划的思维方式。这道题不仅考察算法，更考验我们对问题的建模能力。

🏠 问题的本质

想象你是一位特立独行的小偷，准备沿着一条街偷窃。每间房屋都存放着特定金额的现金，但有一个重要的限制：由于房屋之间有防盗系统，如果偷窃了相邻的房屋就会触发警报。

给你一个数组表示每个房屋的现金数：

输入：[2,7,9,3,1]
输出：12
解释：偷窃 2 + 9 + 1 = 12，这样不会触发相邻房屋的警报

🤔 从直觉到算法

第一步：理解问题的本质

这个问题乍看像是在玩数字游戏，但仔细想想，它其实在问：如何在一系列数字中选择一些不相邻的数，使得它们的和最大？

让我们用动态规划的思维来解析这个问题。记住一个关键点：动态规划的精髓在于，将大问题分解成小问题，并找到这些问题之间的关联。

第二步：寻找状态转移方程

站在当前房屋前，我们面临两个选择：

1. 偷这间房子：那就不能偷前一间，但可以偷前前一间
2. 不偷这间房子：那就可以保持前一间房子的最优结果

这就形成了我们的状态转移方程的雏形。让我们看看如何将这种思维转化为代码：

class Solution {
    // 方法一：基础动态规划解法
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];
        
        // dp[i] 表示偷到第i间房子时能得到的最大金额
        int[] dp = new int[nums.length];
        
        // 初始状态
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        
        // 状态转移
        for (int i = 2; i < nums.length; i++) {
            dp[i] = Math.max(dp[i-1],         // 不偷当前房子
                            dp[i-2] + nums[i]  // 偷当前房子
                           );
        }
        
        return dp[nums.length - 1];
    }
    
    // 方法二：空间优化版本
    public int robOptimized(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];
        
        // 只需要两个变量记录前两个状态
        int prev2 = nums[0];           // dp[i-2]
        int prev1 = Math.max(nums[0], nums[1]); // dp[i-1]
        int current = prev1;
        
        for (int i = 2; i < nums.length; i++) {
            current = Math.max(prev1, prev2 + nums[i]);
            prev2 = prev1;
            prev1 = current;
        }
        
        return current;
    }
}

💡 动态规划的四个关键步骤

通过这道题，我们可以清晰地看到动态规划问题解决的四个步骤：

1. 定义状态

在这个问题中，我们定义 dp[i] 表示"偷到第i间房子时能得到的最大金额"。这个定义既包含了我们要求解的目标（最大金额），也隐含了问题的约束（不能偷相邻房屋）。

2. 确定状态转移方程

dp[i] = max(dp[i-1],          // 不偷第i间房子
            dp[i-2] + nums[i]  // 偷第i间房子
           )

这个方程体现了"偷还是不偷"的两个选择。

3. 初始化基础状态

对于打家劫舍问题：

• dp[0] = nums[0]：只有一间房子时，就偷这间
• dp[1] = max(nums[0], nums[1])：两间房子时，选较大的偷

4. 确定计算顺序

从左到右遍历房子，逐步构建最优解。这个顺序保证了计算某个状态时，它依赖的状态都已经计算出来了。

🔍 空间优化的艺术

注意观察状态转移方程，我们发现每次计算只需要用到前两个状态。这就提供了优化空间的机会：不需要存储整个dp数组，只需要三个变量就够了。这种优化在很多动态规划问题中都很常见。

🎯 举一反三

这个问题的核心思想可以扩展到很多类似场景：

• 打家劫舍 II（房子围成一圈）
• 粉刷房子（每个房子可以刷不同的颜色，相邻不能相同）
• 最大子序列和（可以不连续）

💡 思考题

如果现在不是简单的偷或不偷，而是每间房子都有一个"报警概率"，如何修改我们的动态规划方程？提示：可能需要考虑期望收益。

📝 面试技巧

在面试中遇到这类问题，建议这样展示你的思路：

首先，明确问题的核心约束 - 不能偷相邻房屋。然后，用人性化的语言解释选择 - "对于每间房子，我们面临偷或不偷的选择"。最后，逐步推导出状态转移方程，并解释为什么这个方程是正确的。

记住，动态规划不仅是一种解法，更是一种思维方式。它教会我们如何将复杂问题分解成简单的子问题，并通过巧妙的状态设计找到最优解。

---

作者：忍者算法
公众号：忍者算法

动态规划的美，不仅在于它能解决复杂的问题，更在于它能让我们以优雅的方式思考问题。希望这篇文章能帮助你更深入地理解动态规划的精髓！

#算法面试 #LeetCode #动态规划 #面试高频题