`

House Robber II

阅读更多
Note: This is an extension of House Robber.

After robbing those houses on that street, the thief has found himself a new place for his thievery so that he will not get too much attention. This time, all houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, the security system for these houses remain the same as for those in the previous street.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

House Robber的变形题目,在这个题目中要求收尾两个元素不可以同时选择。我们可以分为两种情况,第一种情况是选择了第一个元素,那么最后一个元素肯定不能选,我们求出这种情况下的最大值max1;第二种情况是不选择第一个元素,那么最后一个元素可以选择,我们同样求出这种情况的下的最大值max2,然后我们返回max1和max2中较大者即可。代码如下:
public class Solution {
    public int rob(int[] nums) {
        if(nums == null || nums.length == 0) return 0;
        if(nums.length == 1) return nums[0];
        if(nums.length == 2) return Math.max(nums[0], nums[1]);
        int max = 0;
        int[] dp = new int[nums.length];
        dp[1] = nums[0];
        for(int i = 2; i < nums.length; i++) {
            dp[i] = Math.max(dp[i - 2] + nums[i - 1], dp[i - 1]);
        }
        max = dp[nums.length - 1];
        Arrays.fill(dp, 0);
        dp[1] = nums[1];
        for(int i = 2; i < nums.length; i++) {
            dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
        }
        return Math.max(max, dp[nums.length - 1]);
    }
}
分享到:
评论

相关推荐

    最大公共字符串leetcode-HouseRobber-Problem-LeetCode-:HouseRobber-问题-LeetCode-

    HouseRobber-问题-LeetCode- @Faizansayeed28 代码 /** * 问题陈述- 你是一名职业劫匪,计划抢劫街道上的房屋。 每个房子都有一定数量的钱 藏起来,阻止你抢劫他们的唯一限制是相邻的房子有安全系统 连接,如果同一...

    python-leetcode题解之213-House-Robber-II.py

    python python_leetcode题解之213_House_Robber_II.py

    2_16337341_朱志儒1

    在本题中,我们讨论了两个经典的动态规划问题,分别是“House Robber II”(#213)和“Triangle”(#120)。这两个问题都涉及到寻找最优策略,通过迭代计算求解。 1. **House Robber II**: 这个问题是“House ...

    python-leetcode题解之198-House-Robber.py

    python python_leetcode题解之198_House_Robber.py

    c语言-leetcode题解之0337-house-robber-iii

    c c语言_leetcode题解之0337_house_robber_iii

    house_robber_family_problems

    标题 "house_robber_family_problems" 暗示我们正在处理一个与计算机科学和编程相关的挑战,可能是算法问题或编程竞赛的题目。这个题目可能源自经典的“打家劫舍”(House Robber)系列问题,这是一个在算法设计中...

    Roberry_house_dynamicprogramming_源码

    在这个场景中,"Roberry_house_dynamicprogramming_源码" 提到的是一个关于房屋盗窃问题的动态规划解决方案,通常被称为“House Robber”问题。这个问题源于LeetCode等在线编程挑战平台,旨在锻炼程序员的逻辑思维和...

    leetcode和oj-OJ_Solution:leetcode、poj等OJ解决方案

    leetcode 和 oj OJ_Solution Solutions for OJ such as leetcode, poj and so on 版本 修改日期 修改人 1 2015-04-16 skymoney ==== ...java/houserobber https://leetcode.com/problems/house-robber/

    lrucacheleetcode-LeetCode:复制和思考

    lru cache leetcode LeetCode copy and think 加油学习 1. 时间轴 时间 题目 描述 知识点 ...House Robber 动态规划 如何确定子问题 20200525 20200525 20200525 20200525 20200525 20200525 $1 234

    gasstationleetcode-leetcode:LeetcodeOJ解决方案

    198.House Robber, 55.Jump Game 72.Edit Distance, 97.Interleaving String, 115.Distinct Subsequences 2017/04/24 (Lintcode)92.Backpack, (Lintcode)125.Backpack II, (Lintcode)564.Backpack VI 不适用 53....

    LeetCode:Leetcode-解决方案

    House Robber [198]6. Range Sum Query - Immutable [303]7. Counting Bits [338]8. Palindromic Substrings [647]9. Maximum Length of Pair Chain [646]10. Integer Break [343]11. Count Numbers with Unique ...

    lrucacheleetcode-LeetCode:CppSourceCode的LeetCode解决方案

    lru cache leetcode LeetCode 解决题目的总数: 136/1753 微信公众号: 工程师Ruojhen 算法-动态规划 题号 名称 English Name 题解 53 最大子序和 Maximum Subarray 70 ...House Robber 213 打家劫舍Ⅱ

    leetcode最大蓄水量-leetcode:记录自己leetocde的过程

    House Robber 学会了数组的创建,以及动态规划最基本的题目 2021.2.2 322 兑换钱币 学会了 Arrays.fill 的使用,以及查看源码,返回 记录在哔哩哔哩 中 2021.2.3 53 最大子数字之和 先更新max,再将负数赋值为0 62 ...

    prac:编码实践

    编码实践 编码实践 模式:二进制搜索: 二进制搜索 二进制搜索: : 排序数组的上限: : ... 众议院强盗2: ://leetcode.com/problems/house-robber-ii/discuss/59921/9-lines-0ms-O(1)-Space-C++-sol

    python-leetcode面试题解之第198题打家劫舍-题解.zip

    本压缩包中的内容是针对LeetCode平台上的第198题“打家劫舍”(House Robber)的Python解决方案。 “打家劫舍”是一道经典的动态规划问题,其核心在于寻找最优策略,即在不触动相邻房屋的情况下,最大化抢劫的财富...

    LeetCode判断字符串是否循环-data-structure-and-algo:C++中的数据结构和算法

    HouseRobber(#198), ClimbingStairs(#70), CoinChange(#322), EditDistance(#72) 图 : 集合的合并(直接求并、按大小求并和按深度求并)、根搜寻(路径压缩) : 有向图和无向图的邻接表表示方法 : 图的深度优先和广度...

    javascript-leetcode面试题解动态规划问题之第198题打家劫舍-题解.zip

    本题解将深入探讨第198题“打家劫舍”(House Robber),这是一个典型的动态规划问题,对于理解该算法模式及其应用至关重要。 动态规划是一种解决最优化问题的方法,通过将大问题分解为更小的子问题来求解。在这个...

    python-leetcode面试题解之第337题打家劫舍III.zip

    在LeetCode平台上,第337题“打家劫舍III”(House Robber III)是一道涉及深度优先搜索(DFS)和树结构的经典算法题。这道题目要求我们通过Python编程来解决一个树形结构下的抢劫问题,旨在考察我们对递归、树遍历...

    JAVA程序设计上机课4_阳甫军‘.pptx

    1. LeetCode 198:House Robber(打家劫舍) - 这是一个经典的动态规划问题,目标是确定在一个房子列表中,不相邻的房子可以被抢劫的最大金额。需要提交代码并附上运行结果截图。 2. LeetCode 349:Intersection ...

Global site tag (gtag.js) - Google Analytics