每日OJ题_简单多问题dp①_力扣LCR 089. 打家劫舍

目录

力扣面试题 17.16. 按摩师

解析代码

力扣LCR 089. 打家劫舍

三道一样/类似的题：

LCR 089. 打家劫舍

198. 打家劫舍

面试题 17.16. 按摩师

难度 中等

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

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

示例 1：

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

示例 2：

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

提示：

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 400

class Solution {
public:
    int rob(vector<int>& nums) {

    }
};

解析代码

以某个位置为结尾，结合题目要求，dp[i] 表示：选择到 i 位置时，此时的最大金额。

但是我们这个题在 i 位置的时候，会面临选择或者不选择两种抉择，所依赖的状态需要细分：

• f[i] 表示：选择到 i 位置时， nums[i] 必选，此时的最大金额；
• g[i] 表示：选择到 i 位置时， nums[i] 不选，此时的最大金额。

因为状态表示定义了两个，因此状态转移方程也要分析两个：

• 对于 f[i] ： 如果 nums[i] 必选，那么仅需知道 i - 1 位置在不选的情况下的最大金额， 然后加上 nums[i] 即可，因此 f[i] = g[i - 1] + nums[i] 。
• 对于 g[i] ： 如果 nums[i] 不选，那么 i - 1 位置上选或者不选都可以。因此，我们需要知道 i - 1 位置上选或者不选两种情况下的最大金额，因此 g[i] = max(f[i - 1], g[i - 1]) 。

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        // f[i], g[i]表示：选择到 i 位置时，此时的最大金额。
        vector<int> f(n);
        auto g = f;
        f[0] = nums[0];
        for (int i = 1; i < n; i++)
        {
            f[i] = g[i - 1] + nums[i];
            g[i] = max(f[i - 1], g[i - 1]);
        }
        return max(f[n - 1], g[n - 1]);
    }
};