每日一题之打家劫舍

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

打家劫舍

题目链接

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

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

示例 1:

输入:[1,2,3,1]
输出:4
解释:偷窃 1 号房屋 (金额 = 1) ,然后偷窃 3 号房屋 (金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 。

示例 2:

输入:[2,7,9,3,1]
输出:12
解释:偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9),接着偷窃 5 号房屋 (金额 = 1)。
     偷窃到的最高金额 = 2 + 9 + 1 = 12 。

提示:

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

这道题目的本质是求一个数组中不相邻元素的最大和。我们可以用动态规划的方法来解决这个问题。动态规划的核心是找出状态转移方程,即如何从已知的子问题的解得到更大的子问题的解。

我们定义dp[i]表示从第0个房屋到第i个房屋能够偷窃到的最高金额,那么我们可以得到以下状态转移方程:

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

这个方程的意思是,对于第i个房屋,我们有两种选择:要么不偷,那么最高金额就是dp[i-1];要么偷,那么最高金额就是dp[i-2]加上当前房屋的金额nums[i]。我们取两者中的较大值作为dp[i]

由于dp[i]只和dp[i-1]dp[i-2]有关,所以我们不需要用一个数组来存储所有的dp值,只需要用两个变量来记录前两个状态即可。这样可以节省空间复杂度。

根据题目的提示,我们还需要考虑数组为空或只有一个元素的情况。这些情况下,我们直接返回0或nums[0]即可。文章来源地址https://www.toymoban.com/news/detail-473982.html

def rob(nums):
    # 如果数组为空,返回0
    if not nums:
        return 0
    # 如果数组只有一个元素,返回该元素
    if len(nums) == 1:
        return nums[0]
    # 初始化前两个状态
    prev = 0 # dp[-1]
    curr = nums[0] # dp[0]
    # 遍历数组,更新状态
    for i in range(1, len(nums)):
        # 计算当前状态
        temp = max(curr, prev + nums[i])
        # 更新前两个状态
        prev = curr
        curr = temp
    # 返回最后一个状态
    return curr

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

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

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

相关文章

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

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

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

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

    2024年02月16日
    浏览(36)
  • 算法训练第四十八天|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日
    浏览(39)
  • 代码随想录刷题第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日
    浏览(62)
  • 【算法|动态规划No.10】leetcode LCR 089. 打家劫舍 & LCR 090. 打家劫舍 II

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

    2024年01月20日
    浏览(44)
  • 198. 打家劫舍

    198. 打家劫舍 https://leetcode.cn/problems/house-robber/description/

    2024年01月20日
    浏览(43)
  • 打家劫舍系列

     

    2024年02月15日
    浏览(39)
  • 打家劫舍 III

    打家劫舍 III 如果 两个直接相连的房子在同一天晚上被打劫 ,房屋将自动报警 返回 在不触动警报的情况下 ,小偷能够盗取的最高金额 记忆化 + 解决重复子问题解决本题,在任意一个位置,小偷可以选择打劫该房屋和不打劫该房屋,如果打劫,则不能打劫该节点下的子节点

    2024年02月09日
    浏览(39)
  • _198打家劫舍

    _198打家劫舍 https://leetcode.cn/problems/house-robber/submissions/496496112/

    2024年01月18日
    浏览(44)
  • 力扣198. 打家劫舍

    Problem: 198. 打家劫舍 1.定义状态: dp[i] 表示从第i个房子开始偷起可以偷得的最大金额数目; 2.状态转移:由于不能连续的偷相邻的两个房子,则为了使得从第i个房子开始偷起是最大金额则要判断 是从当前第i个房子开始偷(代码中表示为nums[i] + dp[i + 2]),还是不偷当前第i个房

    2024年04月25日
    浏览(42)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包