213. 打家劫舍 II

class Solution {
    public int rob(int[] nums) {
        /**

        动态规划 ,更上个题区别是他的首尾相连
        分为两种情况讨论
           0->最后一家前面的那个(你拿了第一个 就不能偷最后一个)
           1->最后一家   
         */ 

         int dp1[]=new int[nums.length];
         int dp2[]=new int[nums.length];
         dp1[0]=0;
         dp2[0]=0;
         if(nums.length==1){
             return nums[0];
         }
         if(nums.length==2){
             return Math.max(nums[0],nums[1]);
         }
         dp1[1]=nums[0];//从0开始
         dp2[1]=nums[1];//从1开始
         for(int i=2;i<nums.length;i++){
             dp1[i]=Math.max(dp1[i-1],dp1[i-2]+nums[i-1]);// num[i-1]是因为nums坐标从0开始
              dp2[i]=Math.max(dp2[i-1],dp2[i-2]+nums[i]);//  num[i]是因为nums坐标从1开始
         }
         return Math.max(dp1[nums.length-1],dp2[nums.length-1]);


    }
}