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;
    } 
    
}