打家劫舍

1. 题目描述

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组，计算你不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

样例输入 #1

输入：[1,2,3,1]

样例输出 #1

输出：4 解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。 偷窃到的最高金额 = 1 + 3 = 4

2. 分析

首先考虑最简单的情况。如果只有一间房屋, 则偷窃该房屋, 可以偷窃到最高总金额。如果只有两间房屋,则由于两间房屋相邻, 不能同时偷窃, 只能偷窃其中的一间房屋, 因此选择其中金额较高的房 屋进行偷窃, 可以偷窃到最高总金额。 如果房屋数量大于两间, 应该如何计算能够偷窃到 的最高总金额呢？ 对于第 k (>2) 间房屋, 有两 个选项：

1. 偷窃第 k 间房屋, 那么就不能偷窃第 k-1 间房屋, 偷窃总金额为前 k-2 间房屋的最高 总金额与第 k 间房屋的金额之和。
2. 不偷窃第 k 间房屋, 偷窃总金额为前 k- 1 间房屋的最高总金额。 在两个选项中选择偷窃总金额较大的选项, 该选项 对应的偷窃总金额即为前 k 间房屋能偷窃到的最 高总金额。 用 dp[i] 表示前i间房屋能偷窃到的最高总金额, 那么就有如下的状态转移方程： dp[i] = max[dpli - 2] + nums[i], dp[i - 1] 边界条件为： dp[0] = nums[0]只有一间房屋,则偷窃该房屋 dp[1] = max[nams[0], nums[1]]只有两间房屋,选择其中金额较高的房屋进行偷窃

3. 代码

 #include <vector>
#include <algorithm>
class Solution {
public:
    int rob(std::vector<int>& nums) {
        int size = nums.size();
        if (size == 0) return 0;
        if (size == 1) return nums[0];
        if (size == 2) return std::max(nums[0], nums[1]);
        
        // Helper function to solve the linear house robber problem
        auto robLinear = [&](int start, int end) {
            std::vector<int> dp(end - start + 1, 0);
            dp[0] = nums[start];
            dp[1] = std::max(nums[start], nums[start + 1]);
            for (int i = 2; i <= end - start; i++) {
                dp[i] = std::max(dp[i - 2] + nums[start + i], dp[i - 1]);
            }
            return dp[end - start];
        };
        
        // Case 1: Rob the first house but not the last house
        int maxRob1 = robLinear(0, size - 2);
        // Case 2: Rob the last house but not the first house
        int maxRob2 = robLinear(1, size - 1);
        
        // Return the maximum of the two cases
        return std::max(maxRob1, maxRob2);
    }
};

一、需要注意的关键问题

1. 边界条件处理

• 空数组情况：当输入数组为空时，直接返回0
• 单元素情况：只有一个房屋时，只能偷这一间
• 两元素情况：选择金额较大的那一间

if not nums:
    return 0
if len(nums) == 1:
    return nums[0]

2. 状态定义的准确性

• 容易混淆 dp[i] 的含义：是前 i 间房屋还是第 i 间房屋
• 索引对应关系：dp[i] 对应 nums[i-1]，需要特别注意数组索引的偏移

3. 状态转移方程的理解

• 核心思想是"偷或不偷"的二元选择
• 容易错误地认为必须间隔固定距离，实际上是要在所有可能的组合中找最优解
• 转移方程：dp[i] = max(dp[i-1], dp[i-2] + nums[i-1])

4. 空间复杂度优化的时机

• 基础DP版本虽然直观，但空间复杂度为O(n)
• 由于状态转移只依赖前两个状态，可以优化到O(1)空间
• 优化时要注意变量更新的顺序，避免覆盖还未使用的值

5. 数据类型和范围考虑

• 题目说明是非负整数，但实际应用中可能需要考虑整数溢出
• 如果金额很大，可能需要使用长整型或其他数据类型

二、解决该问题的启发

1. 动态规划的核心思想

"最优子结构" + "重叠子问题"

• 每个房屋的决策都依赖于前面房屋的最优解
• 通过保存子问题的解避免重复计算
• 启发：面对复杂问题时，思考能否分解为相似的子问题

2. 决策建模的思维方式

"二元选择"模型

• 很多优化问题都可以建模为"选或不选"的决策
• 这种思维方式适用于：背包问题、股票买卖、任务调度等
• 启发：将复杂约束转化为简单的决策选择

3. 状态压缩的通用技巧

滚动数组思想

• 当DP状态只依赖于有限个前面状态时，可以用少数变量替代整个数组
• 这种技巧在斐波那契数列、爬楼梯等问题中同样适用
• 启发：分析状态依赖关系，寻找空间优化的可能性

4. 问题抽象能力

从具体场景到数学模型

• 将"偷房子"的具体场景抽象为"相邻元素不能同时选择"的数学问题
• 这种抽象能力可以应用到：路径规划、资源分配、时间安排等场景
• 启发：遇到实际问题时，尝试剥离具体细节，找到本质的数学结构

5. 边界思维的重要性

极端情况的考虑

• 空输入、单元素、全零等边界情况往往暴露算法缺陷
• 在实际工程中，边界情况处理不当是bug的主要来源
• 启发：设计算法时要主动思考各种边界条件

6. 贪心策略的局限性

为什么不能用贪心？

• 直觉上可能想每次都选最大的，但局部最优≠全局最优
• 例如 [2, 1, 1, 2]：贪心会选择第一个2，但最优解是选择两个2
• 启发：当问题存在"未来影响当前决策"的特性时，贪心往往失效

7. 算法优化的层次性

从正确到高效

• 第一层次：确保算法正确性（基础DP）
• 第二层次：优化空间复杂度（滚动变量）
• 第三层次：考虑实际应用场景的特殊优化
• 启发：算法设计应该循序渐进，先保证正确再追求效率

三、实际应用延伸

这个问题的解决思路可以延伸到很多实际场景：

1. 资源分配：相邻时间段不能同时使用同一资源
2. 投资决策：某些投资项目存在互斥关系
3. 路径规划：某些相邻节点不能同时经过
4. 任务调度：某些任务不能连续执行

通过这个看似简单的"打家劫舍"问题，我们不仅学会了一个具体的算法，更重要的是掌握了解决一类优化问题的通用思维框架。