leetcode 打家劫舍(dp)

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

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

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

示例 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数组

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

省空间做法。考虑到来到当前的一个房屋所能偷到的最大金额只与前两个房间有关,所以我们可以直接采取创建两个变量来保存前两个房间的信息,不断更新即可。文章来源地址https://www.toymoban.com/news/detail-480374.html

class Solution {
public:
    int rob(vector<int>& nums) {
        int len=nums.size();
        if(len==1)
        return nums[0];
        int first=nums[0];
        int second=max(nums[0],nums[1]);
        for(int i=2;i<len;i++){
            int temp=second;
            second=max(nums[i]+first,second);
            first=temp;
        }
        return second;
    }
};

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

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

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

相关文章

  • 力扣hot100 打家劫舍 DP 滚动数组

    Problem: 198. 打家劫舍 👨‍🏫 参考地址 时间复杂度: O ( n ) O(n) O ( n ) 空间复杂度: O ( n ) O(n) O ( n ) 空间复杂度: O ( 1 ) O(1) O ( 1 )

    2024年01月19日
    浏览(42)
  • 【动态规划】简单多状态dp问题(1)打家劫舍问题

    打家劫舍问题 传送门:面试题 17.16. 按摩师 题目: 1.1 题目解析 越难的dp问题,看示例只能起到了解题目的效果,一般推不出啥普遍的规律,所以接下来就是我们的算法原理,通过动归的思想去理解,才会豁然开朗! 1.2 算法原理 1.2.1 状态表示 我们需要通过经验 + 题目要求去

    2024年02月12日
    浏览(43)
  • 【算法】树形DP ② 打家劫舍Ⅲ(树上最大独立集)

    最大独立集 需要从图中选择尽量多的点,使得这些点互不相邻。 337. 打家劫舍 III 用一个数组 int[] = {a, b} 来接收每个节点返回的结果 。返回值{a,b} a表示没选当前节点的最大值,b表示选了当前节点的最大值。 使用 后序遍历 dfs。 ( 发现树形 DP 基本都是后序 dfs ) P1352 没有上

    2024年02月12日
    浏览(44)
  • 【LeetCode题目详解】第九章 动态规划part09 198.打家劫舍 213.打家劫舍II 337.打家劫舍III(day48补)

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

    2024年02月09日
    浏览(46)
  • LeetCode198.打家劫舍

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

    2024年03月12日
    浏览(89)
  • LeetCode - 198 打家劫舍

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

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

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

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

    原题链接:. - 力扣(LeetCode) 小偷又发现了一个新的可行窃的地区。这个地区只有一个入口,我们称之为  root  。 除了  root  之外,每栋房子有且只有一个“父“房子与之相连。一番侦察之后,聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 

    2024年04月15日
    浏览(33)
  • leetcode hot100 打家劫舍

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

    2024年02月19日
    浏览(38)
  • leetcode 2560. 打家劫舍 IV

    2560. 打家劫舍 IV 沿街有一排连续的房屋。每间房屋内都藏有一定的现金。现在有一位小偷计划从这些房屋中窃取现金。 由于相邻的房屋装有相互连通的防盗系统,所以小偷  不会窃取相邻的房屋  。 小偷的  窃取能力  定义为他在窃取过程中能从单间房屋中窃取的  最大金

    2024年02月07日
    浏览(35)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包