【算法|动态规划No.10】leetcode LCR 089. 打家劫舍 & LCR 090. 打家劫舍 II

个人主页：兜里有颗棉花糖
欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 兜里有颗棉花糖 原创
收录于专栏【手撕算法系列专栏】【LeetCode】
🍔本专栏旨在提高自己算法能力的同时，记录一下自己的学习过程，希望对大家有所帮助
🍓希望我们一起努力、成长，共同进步。

一、LCR 089. 打家劫舍

点击可直接跳转到该题目

1️⃣题目描述

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

给定一个代表每个房屋存放金额的非负整数数组 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

2️⃣题目解析

状态转移方程如下：

• f[i] = g[i - 1] + nums[i-1]
• g[i] = max(f[i-1],g[i-1])

状态表示：

• f[i] 表示的是偷取前 i 个房屋中的第 i 个房屋时的最大金额。
• g[i] 表示的是不偷取第 i 个房屋时的最大金额。

3️⃣解题代码

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();

        vector<int> f(n + 1);
        auto g = f;

        for(int i = 1;i <= n;i++)
        {
            f[i] = g[i - 1] + nums[i-1];
            g[i] = max(f[i-1],g[i-1]);
        }
        
        return max(f[n],g[n]);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

代码通过啦：

二、LCR 090. 打家劫舍 II

点击直接跳转到该题目

1️⃣题目描述

一个专业的小偷，计划偷窃一个环形街道上沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

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

示例1：

输入：nums = [2,3,2]
输出：3
解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。

示例2：

输入：nums = [1,2,3,1]
输出：4
解释：你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。偷窃到的最高金额 = 1 + 3 = 4 。

示例3：

输入：nums = [0]
输出：0

注意：

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

2️⃣题目解析

状态表示：

• f[i] 表示偷盗i位置时，偷取i位置，此时的最大金额
• g[i] 表示偷盗i位置时，不偷取i位置，此时的最大金额

这里要分两种情况进行讨论：第一种情况是打劫第一家，第二种情况就是不打劫第一家。

情况1（打劫第一家）：最大总金额 = nums[0] + 街道(2,n-2)的最大总金额

情况2（不打劫第一家）：最大总金额 = 街道(1,n-1)的最大总金额

街道(起始位置，终止位置)的最大总金额这里完全按照打家劫舍 I的方式来求取即可。

最终返回值是两种情况的最大值。

3️⃣解题代码

示例代码1：

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        int ret1 = 0,ret2 = 0;

        // 第一种情况:打劫第一家
        vector<int> f1(n + 1);
        vector<int> g1(n + 1);
        for(int i = 3;i <= n-1;i++)
        {
            f1[i] = nums[i - 1] + g1[i-1];
            g1[i] = max(f1[i-1],g1[i-1]);
        }
        ret1 = max(f1[n-1],g1[n-1]) + nums[0];
        // 第二种情况:不打劫第一家
        vector<int> f2(n + 1);
        vector<int> g2(n + 1);
        for(int i = 2;i <= n;i++)
        {
            f2[i] = nums[i - 1] + g2[i-1];
            g2[i] = max(f2[i-1],g2[i-1]);
        }
        ret2 = max(f2[n],g2[n]);

        return max(ret1,ret2);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

示例代码2：

class Solution {
public:
    int rob(vector<int>& nums) 
    {
        int n = nums.size();
        int ret = max((rob1(nums,2,n-2) + nums[0]),rob1(nums,1,n-1));
        return ret;
    }

    int rob1(vector<int> nums,int l,int r)
    {
        if(l>r) return 0;
        int n = nums.size();
        vector<int> f(n);
        auto g = f; 
        f[l] = nums[l];
        for(int i = l + 1 ;i <= r;i++)
        {
            f[i] = nums[i] + g[i-1];
            g[i] = max(g[i-1],f[i-1]);
        }
        return max(f[r],g[r]);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

通过：