`
hcx2013
  • 浏览: 82146 次
社区版块
存档分类
最新评论

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 

 

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]);
        }
        return Math.max(rob1(nums, 0, nums.length-2), rob1(nums, 1, nums.length-1));
    }
    public int rob1(int[] nums, int s, int e) {
        int[] dp = new int[e-s+1];
        dp[0] = nums[s];
        dp[1] = Math.max(nums[s], nums[s+1]);
        for (int i = 2; i < dp.length; i++) {
			dp[i] = Math.max(dp[i-2] + nums[s+i], dp[i-1]);
		}
        return dp[dp.length-1];
    }
}

 

分享到:
评论

相关推荐

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

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

    cpp-算法精粹

    House Robber II House Robber III Range Sum Query - Immutable Range Sum Query 2D - Immutable 图 Clone Graph 位操作 Reverse Bits Repeated DNA Sequences Number of 1 Bits Gray Code Single Number Single ...

    house_robber_family_problems

    house_robber_family_problems

    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

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

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

Global site tag (gtag.js) - Google Analytics