213. House Robber II

https://leetcode.com/problems/house-robber-ii/

跟house robber i 没有任何区别其实，关键在于rob 0-n-2的house，或者rob 1-n-1的house，因为0和n-1不能一起rob

class Solution {
    public int rob(int[] nums) {
        if (nums.length == 1) {
            return nums[0];
        }
        if (nums.length == 2) {
            return Math.max(nums[0], nums[1]);
        }
        return Math.max(rob(nums, 0, nums.length-2), rob(nums, 1, nums.length-1));
    }
    // rob可以用O(n)做的噢
    private int rob(int[] nums, int start, int end) {
        if (end == start + 1) {
            return Math.max(nums[start], nums[end]);
        }
        int[] dp = new int[end-start+1];
        dp[0] = nums[start];
        dp[1] = nums[start+1];
        int max = Math.max(dp[0],dp[1]);
        for (int i = start+2; i <= end; i++) {
            int idx = i - start;
            for (int j = idx - 2; j >= 0; j--) {
                dp[idx] = Math.max(dp[idx], nums[i] + dp[j]);
            }
            max = Math.max(max, dp[idx]);
        }
        return max;
    }
}