198 打家劫舍

题目信息

题目地址:https://leetcode-cn.com/problems/house-robber/

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

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

示例 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 。

提示:

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

解法一:动态规划

由题知道我们的这个小偷他偷一家必须得至少隔一家再偷不能连着偷,那我们可以从最简单的来推导看看:

一条街
一开始只有一家:2块
后来搬来了一家有钱人:7块
后来陆陆续续来了几家:3块、4块、5块

那只有一家的时候只能偷2块 f(1) = 2 有两家了进行一次选择挑个富的 f(2) = max(第一家,第二家) = 7 有三家的时候也要进行一次选择 f(3) = max(f(1)+第三家,f(2)) = 7 到这个地方其实就出来了表达式 dp[i] = max(dp[i - 2] + nums[i] , dp[i - 1]) 存储之前的结果推导下一个结果,也就是动态规划过滤掉一半的组合。比如(2,7,3,4)对于(2,7,3)我们已经得到最大方案是7并记录了,那么与第四家4块结合的必不是(2、3)里的。4家虽然有三种组合但(2+4)这种组合就不会出现在计算中

动态规划每次记录之前的偷的最多与前前偷的最多的值,进行取舍,要么是前前的累计最大金额算上当前房子大要么就还是之前的最大,避免树形展开

所以我们要准备存两个量一个是最新的最大金额也就是结果,要动态的选择结果还要一个前几个房子的最大金额,来决定下次偷还是不偷

代码如下:

class Solution {
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        if (nums.length == 1) {
            return nums[0];
        }
        // 两个量:到目前累计最大与之前房屋累计最大
        int[] dp = [nums[0],Math.max(nums[0],nums[1])];
        for (int i = 2; i < length; i++) {
            // 扫描到下一个了,两个量按次序变换
            int temp = dp[1];
            second = Math.max(dp[0] + nums[i], dp[1]);
            dp[0] = temp;
        }
        return result;
    }
}

总结

其实这题和之前写的爬楼梯比较像,可以对照着总结。总体来说第一就是dp表也就是备忘录解决子问题重叠,第二就是空间的压缩我们需要明白是否必要存每个子问题的结果。

- END -

本文分享自微信公众号 - IT那个小笔记(Jasper-zh_blog),作者:木瓜煲鸡脚

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2021-03-01

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 198. 打家劫舍

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

    lucifer210
  • 198. 打家劫舍

    CaesarChang张旭
  • 力扣198——打家劫舍

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

    健程之道
  • LeetCode 198. 打家劫舍(DP)

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

    Michael阿明
  • 画解算法:198. 打家劫舍

    https://leetcode-cn.com/problems/house-robber/

    灵魂画师牧码
  • ​LeetCode刷题实战198:打家劫舍

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就...

    程序IT圈
  • 【LeetCode】198. 打家劫舍 递归递推

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

    韩旭051
  • Leetcode|线性排列|198. 打家劫舍

    《Leetcode|线性排列|198. 打家劫舍》 《Leetcode|环形排列|213. 打家劫舍 II》 《Leetcode|树形排列|337. 打家劫...

    SL_World
  • 每日一题 | Python3 实战 LeetCode 「198. 打家劫舍 」& 「213. 打家劫舍 II」

    https://leetcode-cn.com/problems/house-robber/

    与你一起学算法
  • LeetCode - 198 简单动态规划 打家劫舍

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

    梅花
  • Leetcode|环形排列|213. 打家劫舍 II

    《Leetcode|线性排列|198. 打家劫舍》 《Leetcode|环形排列|213. 打家劫舍 II》 《Leetcode|树形排列|337. 打家劫...

    SL_World
  • LeetCode131|打家劫舍

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

    码农王同学
  • Leetcode|树形排列|337. 打家劫舍 III

    《Leetcode|线性排列|198. 打家劫舍》 《Leetcode|环形排列|213. 打家劫舍 II》 《Leetcode|树形排列|337. 打家劫...

    SL_World
  • 【每日算法Day 104】偷电瓶的周某今天放出来了,还不赶紧做这道题防范一下!

    你是一个专业的小偷,计划偷窃沿路的电瓶车电瓶。每个电瓶价值不一样,影响你偷窃的唯一制约因素就是相邻的电瓶车装有相互连通的防盗系统,如果两辆相邻的电瓶车的电瓶同时...

    godweiyang
  • LeetCode337. 打家劫舍 III

    mathor
  • 213. 打家劫舍 II

    CaesarChang张旭
  • LeetCode 213. 打家劫舍 II(DP)

    你是一个专业的小偷,计划偷窃沿街的房屋,每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈,这意味着第一个房屋和最后一个房屋是紧挨着的。同时,相邻的房屋装有...

    Michael阿明
  • leetcode打家劫舍问题

    https://leetcode-cn.com/problems/house-robber/description/

    程序员小王
  • LeetCode--打家劫舍问题

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

    宇宙之一粟

扫码关注云+社区

领取腾讯云代金券