LeetCode213.House-Robber-II<打家劫舍II>

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

题目:

LeetCode213.House-Robber-II<打家劫舍II>,算法,leetcode,数据结构,c++

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

思路:

在版本一中增加了一个条件 那就是首尾相关联。那么只需要进行两次循环即可。

第一次是循环是偷第一家的 那么循环到n-1 截至 并且保存一个cmp

第二次循环是不偷第一家的 循环到n截至。然后比较cmp 与 dp [n] 的最大值即可。

LeetCode213.House-Robber-II<打家劫舍II>,算法,leetcode,数据结构,c++

 

代码是:

//code
 
class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size()-1;
        if(n==1) return max(nums[0],nums[1]);
        if(n==0) return nums[0];
        int dp[1000]={0};
        dp[0]=nums[0];
        dp[1]=max(dp[0],nums[1]);
        for(int i=2;i<n;i++){
            dp[i]=max(dp[i-2]+nums[i],dp[i-1]);
        }
        int cmp = dp[n-1];
        dp[0]=0;
        dp[1]=nums[1];
        for(int i=2;i<=n;i++){
            dp[i]=max(dp[i-2]+nums[i],dp[i-1]);
        }
        return max(cmp,dp[n]);
    }
};

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

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

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

相关文章

  • 【LeetCode题目详解】第九章 动态规划part09 198.打家劫舍 213.打家劫舍II 337.打家劫舍III(day48补)

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

    2024年02月09日
    浏览(44)
  • 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)
  • LeetCode2560. House Robber IV——二分答案+动态规划

    There are several consecutive houses along a street, each of which has some money inside. There is also a robber, who wants to steal money from the homes, but he refuses to steal from adjacent homes. The capability of the robber is the maximum amount of money he steals from one house of all the houses he robbed. You are given an integer array nums representi

    2024年02月21日
    浏览(34)
  • 算法刷题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)
  • Golang每日一练(leetDay0075) 打家劫舍II、最短回文串

    目录 213. 打家劫舍 II House Robber ii  🌟🌟 214. 最短回文串 Shortest Palindrome  🌟🌟🌟 🌟 每日一练刷题专栏 🌟 Rust每日一练 专栏 Golang每日一练 专栏 Python每日一练 专栏 C/C++每日一练 专栏 Java每日一练 专栏 你是一个专业的小偷,计划偷窃沿街的房屋,每间房内都藏有一定的

    2024年02月06日
    浏览(45)
  • 打家劫舍 II问题的动态规划解决方案及C++代码实现

    解决打家劫舍 II问题涉及动态规划,将环形问题转化为两个单排问题。通过状态转移方程和初始化,计算可以偷窃到的最高金额。C++代码实现包括状态显示、状态转移方程、初始化、填表顺序和返回值。

    2024年01月21日
    浏览(47)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包