`

House Robber

阅读更多
 
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

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.

 大意 ,数组中不能够同时取相邻的两个,能够得到最大和。

 思路 :

    当你要求n个房间时的最大财富是,就要考虑 n - 1 和 n - 2两种情况。

    可以得到递推公式:

T(n) = Max(T(n - 1) , T(n -2) + nums[n])

   可能会觉得,n - 1的时候,你也可以 + nums[n] , 但是那样的话,不就是等于T(n - 2) + nums[i] 最后结果还是没变的

   实际上这里考虑的是 , 求 n 的时候,分上一次邻近与不邻近。

 

public class Solution {
    public int rob(int[] nums) {
        int len = nums.length;
        int pre = 0;
        int cur = 0;
        for(int i = 0 ; i < len ; i++) {
            int tmp = cur;
            cur = Math.max(pre + nums[i] , cur);
            pre = tmp;
        }
        return cur;
    }
}

 

   House Robber II

   问题:

   现在房屋不是在一条直线上 ,而是成一个圆圈。

   分析:

   就得分两种情况来考虑,一种就是包含起点,一种是一定不包含起点。

   所以,就对数组中0 .... n - 2 个元素 进行HouseRobber I 中的求解,求得n - 2时的值

   然后,再对1 .... n - 1 houseRobber I , 求的n - 1时的值,再与 n -2 比较, 就求的max.

   但是这个地方可能会觉的,n - 2时的值,可能也没有包含nums[0] , 那么这时候也可以与

    nums[n -1]相加啊?

   ---- 如果 n - 2 的没有包括nums[ 0] , 那么 n - 2 不就等于 1... n - 1中的n - 2吗?

 

   综上,0 ..... n - 2 : 包括所有从起点开始的max

            1....... n - 1 :一定不包括从起点开始的max.

 

public class Solution {
    public int rob(int[] nums) {
        int len  = nums.length;
        if(len == 0) return 0;
        if(len == 1) return nums[0];
        int startOne = robHouseInNoCircle(nums , 0 , len - 2);
        int startTwo = robHouseInNoCircle(nums, 1 , len - 1);
        return Math.max(startOne , startTwo);
    }
    
    int robHouseInNoCircle(int[] nums , int low , int high) {
        int cur = 0;
        int pre = 0;
        
        for(int i = low ; i <= high ; i++ ) {
            int tmp = cur;
            cur = Math.max(pre + nums[i] , cur);
            pre = tmp;
        }
        
        return cur;
    } 
    
}
 

 

 

  

分享到:
评论

相关推荐

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

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

    cpp-算法精粹

    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 Number II Single ...

    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/

    house_robber_family_problems

    house_robber_family_problems

    lrucacheleetcode-LeetCode:复制和思考

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

    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 打家劫舍Ⅱ

    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:记录自己leetocde的过程

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

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

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

    prac:编码实践

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

Global site tag (gtag.js) - Google Analytics