House Robber II.java

// https://leetcode.com/problems/house-robber-ii/
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]);
        
        if(nums.length == 3) return Math.max(nums[0], Math.max(nums[1], nums[2]));
        
            
        int dp[] = new int[nums.length];
        
        dp[0] = nums[0];
        dp[1] = nums[1];
        dp[2] = nums[0] + nums[2];
        
        for(int i = 3; i < nums.length - 1; i++)
        {
            dp[i] += Math.max(dp[i - 2], dp[i - 3]) + nums[i];
        }
        
        int ans1 = Math.max(dp[dp.length - 2], dp[dp.length - 3]);
        
        dp[1] = nums[1];
        dp[2] = nums[2];
        dp[3] = nums[1] + nums[3];
            
        for(int i = 4; i < nums.length; i++)
        {
            dp[i] = 0;
            dp[i] += Math.max(dp[i - 2], dp[i - 3]) + nums[i];
        }
        
        int ans2 = Math.max(dp[dp.length - 1], dp[dp.length - 2]);
        
        return Math.max(ans1, ans2);
    }
}