每日一题之打家劫舍II

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

题目链接

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

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

示例 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 = [1,2,3]
输出:3

提示:

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

这个问题的关键是如何处理房屋围成一圈的情况。如果房屋是线性排列的,那么问题就比较简单,可以用动态规划的方法解决。动态规划的思想是,用一个数组dp来记录每间房屋能偷到的最大金额,然后根据状态转移方程来更新dp。状态转移方程是:

dp[i] = max(dp[i-1], dp[i-2] + nums[i])

这个方程的意思是,对于第i间房屋,有两种选择:偷或不偷。如果偷,那么就不能偷第i-1间房屋,所以最大金额是dp[i-2] + nums[i];如果不偷,那么就可以偷第i-1间房屋,所以最大金额是dp[i-1]。我们要取两者的较大值作为dp[i]

但是,如果房屋是围成一圈的,那么就不能同时偷第一间和最后一间房屋,否则会触发报警。

所以,我们要将问题分解为两个子问题:偷第一间到倒数第二间房屋,或者偷第二间到最后一间房屋。这样就相当于把圆形的房屋变成了两个线性排列的房屋,然后分别用动态规划的方法求解,最后取两者的较大值作为最终答案。文章来源地址https://www.toymoban.com/news/detail-476891.html

# 定义一个函数,用来计算不围成一圈时的最大金额
def rob(nums):
    # 如果没有房屋,返回0
    if not nums:
        return 0
    # 如果只有一间房屋,返回它的金额
    if len(nums) == 1:
        return nums[0]
    # 初始化动态规划数组
    dp = [0] * len(nums)
    # 第一间房屋只能偷它自己
    dp[0] = nums[0]
    # 第二间房屋可以选择偷或不偷
    dp[1] = max(nums[0], nums[1])
    # 从第三间房屋开始,可以选择偷或不偷,取决于前两间房屋的最大金额
    for i in range(2, len(nums)):
        dp[i] = max(dp[i-1], dp[i-2] + nums[i])
    # 返回最后一间房屋的最大金额
    return dp[-1]

# 定义一个函数,用来计算围成一圈时的最大金额
def rob_circle(nums):
    # 如果没有房屋,返回0
    if not nums:
        return 0
    # 如果只有一间房屋,返回它的金额
    if len(nums) == 1:
        return nums[0]
    # 如果有两间或以上的房屋,分为两种情况:偷第一间到倒数第二间,或者偷第二间到最后一间
    return max(rob(nums[:-1]), rob(nums[1:]))

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

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

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

相关文章

  • 【四】【C语言\动态规划】地下城游戏、按摩师、打家劫舍 II,三道题目深度解析

    动态规划就像是解决问题的一种策略,它可以帮助我们更高效地找到问题的解决方案。这个策略的核心思想就是将问题分解为一系列的小问题,并将每个小问题的解保存起来。这样,当我们需要解决原始问题的时候,我们就可以直接利用已经计算好的小问题的解,而不需要重

    2024年02月04日
    浏览(45)
  • 算法刷题Day 48 打家劫舍+打家劫舍II+打家劫舍III

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

    2024年02月16日
    浏览(35)
  • 算法训练第四十八天|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)
  • 213. 打家劫舍 II

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

    2024年02月06日
    浏览(44)
  • 代码随想录刷题第48天|LeetCode198打家劫舍、LeetCode213打家劫舍II、LeetCode337打家劫舍III

    1、LeetCode198打家劫舍 题目链接:198、打家劫舍 1、dp[i]:考虑下标i(包括i)以内的房屋,最多可以偷窃的金额为dp[i] 。 2、递推公式: 如果偷第i房间,那么dp[i] = dp[i - 2] + nums[i] ; 如果不偷第i房间,那么dp[i] = dp[i - 1]; 然后dp[i]取最大值,即dp[i] = max(dp[i - 2] + nums[i], dp[i - 1

    2024年02月08日
    浏览(58)
  • 【算法|动态规划No.10】leetcode LCR 089. 打家劫舍 & LCR 090. 打家劫舍 II

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

    2024年01月20日
    浏览(43)
  • leetcode 213. 打家劫舍 II

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

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

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

    2024年02月15日
    浏览(40)
  • Java 动态规划 Leetcode 213. 打家劫舍 II

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

    2024年02月13日
    浏览(39)
  • LeetCode213.House-Robber-II<打家劫舍II>

      在版本一中增加了一个条件 那就是首尾相关联。那么只需要进行两次循环即可。 第一次是循环是偷第一家的 那么循环到n-1 截至 并且保存一个cmp 第二次循环是不偷第一家的 循环到n截至。然后比较cmp 与 dp [n] 的最大值即可。  

    2024年02月16日
    浏览(42)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包