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

这篇具有很好参考价值的文章主要介绍了【算法|动态规划No.10】leetcode LCR 089. 打家劫舍 & LCR 090. 打家劫舍 II。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

个人主页:兜里有颗棉花糖
欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 兜里有颗棉花糖 原创
收录于专栏【手撕算法系列专栏】【LeetCode】
🍔本专栏旨在提高自己算法能力的同时,记录一下自己的学习过程,希望对大家有所帮助
🍓希望我们一起努力、成长,共同进步。
【算法|动态规划No.10】leetcode LCR 089. 打家劫舍 & LCR 090. 打家劫舍 II,LeetCode,手撕算法系列专栏,算法,动态规划,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]);
    }
};

代码通过啦:
【算法|动态规划No.10】leetcode LCR 089. 打家劫舍 & LCR 090. 打家劫舍 II,LeetCode,手撕算法系列专栏,算法,动态规划,leetcode

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

示例代码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]);
    }
};

通过:
【算法|动态规划No.10】leetcode LCR 089. 打家劫舍 & LCR 090. 打家劫舍 II,LeetCode,手撕算法系列专栏,算法,动态规划,leetcode文章来源地址https://www.toymoban.com/news/detail-807298.html

到了这里,关于【算法|动态规划No.10】leetcode LCR 089. 打家劫舍 & LCR 090. 打家劫舍 II的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • Java 动态规划 Leetcode 213. 打家劫舍 II

    代码展示:         该题其实是Java 动态规划 面试题 17.16. 按摩师的变种,增加了一个首尾是相邻的条件,而我们解决该题也要用到链接的这道题的思想,可以先去看一下上面这篇博客 此题可以采用动态规划的方法进行解决,根据解决动态规划题目的5大步骤进行逐步分析

    2024年02月13日
    浏览(39)
  • 【LeetCode动态规划#11】打家劫舍系列题(涉及环结构和树形DP的讨论)

    力扣题目链接(opens new window) 你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。 给定一个代表每个房屋存放金额的非

    2023年04月21日
    浏览(37)
  • 【算法|动态规划No.17】leetcode64. 最小路径和

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

    2024年02月07日
    浏览(48)
  • 【算法|动态规划系列No.5】leetcode62. 不同路径

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

    2024年02月12日
    浏览(43)
  • 【算法|动态规划No.6】leetcode63. 不同路径Ⅱ

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

    2024年02月16日
    浏览(48)
  • 【算法|动态规划No.7】leetcode300. 最长递增子序列

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

    2024年02月07日
    浏览(46)
  • 【算法|动态规划No.12】leetcode152. 乘积最大子数组

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

    2024年02月08日
    浏览(44)
  • 【算法|动态规划No.15】leetcode1035. 不相交的线

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

    2024年02月06日
    浏览(44)
  • Day 42 算法记录|动态规划 09 (打家劫舍)

    1.dp[i]:考虑下标i(包括i)以内的房屋,最多可以偷窃的金额为dp[i]。 2.dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]); 3.初始化,dp[0] 和 dp[1],dp[0] 一定是 nums[0],dp[1] = max(nums[0], nums[1]); 3.遍历顺序,dp[i] 是根据dp[i - 2] 和 dp[i - 1] 推导出来的,那么一定是从前到后遍历! 进一步对滚动数组

    2024年02月15日
    浏览(34)
  • 【算法|动态规划No30】leetcode5. 最长回文子串

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

    2024年02月08日
    浏览(40)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包