leetcode 213. 打家劫舍 II

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

2023.8.20

leetcode 213. 打家劫舍 II,leetcode专栏,leetcode,算法,职场和发展,c++,数据结构

         本题是 打家劫舍 的进阶版,房屋之间形成一个环了,也就是第一个房屋和最后一个房屋不能一起偷了。那么能偷的情况分为下列三种:

  1. 不考虑偷首房间。
  2. 不考虑偷尾房间。
  3. 不考虑偷首尾房间。

        第三种情况包含于第一和第二种情况了,所以分别为第一种和第二种情况设两个dp数组,再用昨天 打家劫舍 的思路做就行。 下面上代码:

class Solution {
public:
    int rob(vector<int>& nums) {
        if(nums.size()==0) return 0;
        if(nums.size()==1) return nums[0];
        vector<int> dp1(nums.size());
        vector<int> dp2(nums.size());
        dp1[0] = dp2[0] = 0;
        dp1[1] = nums[0];
        dp2[1] = nums[1];
        for(int i=2; i<=nums.size()-1; i++)
        {
            dp1[i] = max(dp1[i-1] , dp1[i-2]+nums[i-1]);
        }
        for(int i=2; i<=nums.size()-1; i++)
        {
            dp2[i] = max(dp2[i-1] , dp2[i-2]+nums[i]);
        }
        if(dp1[nums.size()-1] > dp2[nums.size()-1]) return dp1[nums.size()-1];
        else return dp2[nums.size()-1];
    }
};

        附上打的草稿以供参考:

leetcode 213. 打家劫舍 II,leetcode专栏,leetcode,算法,职场和发展,c++,数据结构

 文章来源地址https://www.toymoban.com/news/detail-662873.html

到了这里,关于leetcode 213. 打家劫舍 II的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 213. 打家劫舍 II

    关于此题 我的往期文章,动规五部曲详解篇 : leetCode 213. 打家劫舍 II 动态规划 房间连成环怎么偷呢?_呵呵哒( ̄▽ ̄)\\\"的博客-CSDN博客 https://heheda.blog.csdn.net/article/details/133409962 213. 打家劫舍 II - 力扣(LeetCode) 你是一个专业的小偷,计划偷窃沿街的房屋,每间房内都藏有一定

    2024年02月06日
    浏览(41)
  • 算法训练第四十八天|198.打家劫舍、213.打家劫舍II、337.打家劫舍III

    题目链接:198.打家劫舍 参考:https://programmercarl.com/0198.%E6%89%93%E5%AE%B6%E5%8A%AB%E8%88%8D.html 你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入

    2023年04月16日
    浏览(37)
  • 【算法|动态规划No.10】leetcode LCR 089. 打家劫舍 & LCR 090. 打家劫舍 II

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

    2024年01月20日
    浏览(43)
  • 算法刷题Day 48 打家劫舍+打家劫舍II+打家劫舍III

    分成两段来处理:比如说输入的长度是n(0~n-1),就分成[0, n - 1)和[1, n)两部分 写一个辅助函数,返回两个状态,抢或者不抢能得到的最大收获。

    2024年02月16日
    浏览(33)
  • 【学会动态规划】打家劫舍 II(12)

    目录 动态规划怎么学? 1. 题目解析 2. 算法原理 1. 状态表示 2. 状态转移方程 3. 初始化 4. 填表顺序 5. 返回值 3. 代码编写 写在最后: 学习一个算法没有捷径,更何况是学习动态规划, 跟我一起刷动态规划算法题,一起学会动态规划! 题目链接:213. 打家劫舍 II - 力扣(Lee

    2024年02月15日
    浏览(39)
  • 每日一题之打家劫舍II

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

    2024年02月08日
    浏览(40)
  • LeetCode - 198 打家劫舍

    目录 题目来源 题目描述 示例 提示 题目解析 算法源码 题目来源 198. 打家劫舍 - 力扣(LeetCode) 题目描述 你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在

    2023年04月08日
    浏览(30)
  • LeetCode198.打家劫舍

    你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统, 如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组, 计算你 不触动

    2024年03月12日
    浏览(87)
  • leetcode 打家劫舍(dp)

    你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动

    2024年02月08日
    浏览(35)
  • leetcode hot100 打家劫舍

    本题中,依旧可以发现,当前位置的金额受到前两个位置金额是否被偷的影响,所以这明显是动态规划的问题。 我们采用动态规划五部曲来进行做 首先我们确定dp数组的含义:考虑下标i(包括i)以内的房屋,最多可以偷窃的金额为dp[i]。 注意,这里是考虑!那么就说明我这

    2024年02月19日
    浏览(37)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包