打家劫舍

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);
    }
};