213. House Robber II

好像是二刷。

题干改变的一点就是现在所有房子成环了，首尾相连。

现在没法用动态规划来dp[n] 来做了，因为第(n-1)个房子和第1个房子是相连的。

假如我们第一个房子不抢，从n = 1开始，那么剩下的总共n - 1个房子和第一题一样，因为最后一个房子此时就算选了也不和n=0（第一个）重合。

假如我们第一个房子抢，那就只能抢到第n-2个房子，因为就算第一个抢了，也不会影响第n-1个。

就这2种情况。

做的时候用start标记从0还是1开始抢。

Time: O(n)

有些Edge cases需要注意，一个是数组运算到的总数是n-2，因为我们现在2种情况要么不抢第一个，要么不抢最后一个，所以会比上轮上一个

public class Solution {
    public int rob(int[] nums) {
        if (nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];
        if (nums.length == 2) return Math.max(nums[0], nums[1]);
        
        int sol1 = helper(0, nums);
        int sol2 = helper(1, nums);
        return Math.max(sol1, sol2);
    }
    
    public int helper(int start, int[] nums) {
        int[] dp = new int[2];
        dp[0] = nums[start];
        dp[1] = Math.max(nums[start], nums[start + 1]);
        
        for (int i = 2; i < nums.length - 1; i++) {
            dp[i % 2] = Math.max(dp[(i-1)%2], dp[(i-2)%2] + nums[i + start]);
        }
        
        return dp[(nums.length - 2) % 2];
    }
}