力扣第198题 打家劫舍

前言

记录一下刷题历程 力扣第198题 打家劫舍

打家劫舍

原题目：你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

示例 1：

输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。
示例 2：

输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
偷窃到的最高金额 = 2 + 9 + 1 = 12 。

分析

我们画一个决策树来看一下

因为题中说不能偷相邻的两个房屋 所以通过图我们可以看出来 当我们不偷最后一间房子时 偷四间房屋获得的最大利润就变成偷前三间房屋能获得的最大利润。假如我们偷最后一间房屋，那么倒数第二间房屋就不能偷了，那么问题就变为偷到前两间房屋能获得的最大金额加上偷到最后一间房屋的最大金额。同样的针对子数组[1,2,3],我们也可以选择偷最后一间房子，也可以选择不偷。就这样层层分解下去一直到没有房屋可偷或者只剩下一间房子可以偷，可以看到整个过程是存在递归结构的，并且存在重复的子数组[1，2]
和[1],所以既有递归结构又有可以记忆化的重复子问题这就是一道动态规划问题。根据上面的抉择树我们可以得到两个递推公式1.dp[n]=max{dp[n-1],dp[n-2]+nums[n]} 2.dp[0]=0,dp[1]=nums[0]. 根据这两个递推公式我们编写代码。

代码如下：

class Solution {
public:
    int rob(vector<int>& nums) {
        // 创建一个与 nums 大小相同的 dp 数组，用来存储每个位置的最大抢劫金额
        vector<int> dp(nums.size() + 1, 0);
        
        // 如果 nums 数组不为空，则初始化 dp 数组的第一个有效位置
        if (nums.size() > 0) {
            dp[1] = nums[0]; // dp[1] 代表抢劫第一个房子的最大金额
        }

        // 从第二个房子开始，计算每个房子抢劫的最大金额
        for (int i = 2; i < nums.size() + 1; i++) {
            // dp[i-1] 表示不抢劫当前房子时的最大金额
            // dp[i-2] + nums[i-1] 表示抢劫当前房子时的最大金额（不能抢劫 i-1 房子，所以加上 dp[i-2]）
            dp[i] = max(dp[i - 1], dp[i - 2] + nums[i - 1]);
        }

        // 返回抢劫所有房子的最大金额
        return dp[nums.size()];
    }
};

解释注释

1.初始化动态规划数组：

创建一个 dp 数组，长度为 nums.size() + 1，用于存储每个房子被抢劫时的最大金额。初始化为 0。

2.处理边界情况：

如果房子的数量大于 0（即数组 nums 不为空），将第一个房子抢劫的最大金额设为 nums[0]，即 dp[1] = nums[0]。

3.动态规划填表：

从第二个房子开始，依次计算每个房子被抢劫的最大金额。
dp[i] 代表抢劫前 i 个房子的最大金额。
对于每个房子 i，你有两个选择：
不抢劫当前房子 i，则最大金额为 dp[i - 1]。
抢劫当前房子 i，则不能抢劫前一个房子 i - 1，最大金额为 dp[i - 2] + nums[i - 1]。
选择其中较大的一个作为 dp[i] 的值。

4.返回结果：

返回 dp[nums.size()]，即抢劫所有房子时能获得的最大金额。