213. House Robber II

All houses at this place are arranged in a circle. That means the first house is the neighbor of the last one.

so it means, we can define two cases with House Rober 1

1. rob first house

2. rob last house

solution:

dpFunction is the solution of 198. House Robber

Math.max(dpFunction(rob first house), dpFunction(rob last house))

time: O(n)

space: O(n)

class Solution {
    public int rob(int[] nums) {
        // arranged in a circle.
        // 1. steal first house
        // 2. steal last house
        if (nums == null || nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];
        
        return Math.max(robDP(Arrays.copyOfRange(nums, 0, nums.length - 1)), robDP(Arrays.copyOfRange(nums, 1, nums.length)));
    }
    
    public int robDP(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];
        
        int n = nums.length;
        int dp[] = new int[n];
        
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        int res = Math.max(dp[0], dp[1]);
        
        for (int i = 2 ; i < nums.length; i++) {
            dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i]);
            res = Math.max(res, dp[i]);
        }
        return res;
    }
}

----

time: O(n)

space:O(1)

class Solution {
    public int rob(int[] nums) {
        // arranged in a circle.
        // 1. steal first house
        // 2. steal last house
        if (nums == null || nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];
        
        return Math.max(robDP(Arrays.copyOfRange(nums, 0, nums.length - 1)), robDP(Arrays.copyOfRange(nums, 1, nums.length)));
    }
    
    public int robDP(int[] nums) {
        int prevMax = 0;
        int currMax = 0;
        
        for (int num : nums) {
            int temp = currMax;
            currMax = Math.max(currMax, prevMax + num);
            prevMax = temp;
        }
        return currMax;
    }
}

use this one!

class Solution {
    public int rob(int[] nums) {
        if (nums.length == 1) {
            return nums[0];
        }
        return Math.max(
            rob(nums, 0, nums.length-2), 
            rob(nums, 1, nums.length-1)
        );
    }
    private int rob(int[] nums, int start, int end) {
        int dpi2 = 0;
        int dpi1 = 0;
        int dpi = 0;
        
        for (int i = end; i >= start; i--) {
            dpi = Math.max(dpi1, nums[i] + dpi2);
            dpi2 = dpi1;
            dpi1 = dpi;
        }
        return dpi;
    }
}

/*
so the range become different

 n       n 
[x,x,x,x,x]
 n
         n
         
3 cases to match questions

so we can only 
max(
rob(1 ~ n-1),
rob(1 ~ n)
rob(0 ~ n-1)
)
compare which one is bigger

we can ignore this one, rob(1 ~ n-1), this one must be smaller than other 2.

*/