动态规划中等 leetcode213. 打家劫舍 II

import java.lang.Math;
class Solution {
    /*
    与打家劫舍I的区别是偷了第一家就不能偷最后一家。
    因此分为两种情况：不偷第一家（只计算0~n-1家偷的最高金额）；
    不偷最后一家（只计算1~n家偷的最高金额）。
    */
    public int rob(int[] nums) {
       int n=nums.length;
       if(n==0){//注意排除掉0，1，2这三种特殊情况
            return 0;
       }
       if(n==1){
           return nums[0];
       }
       if(n==2){
           return Math.max(nums[0],nums[1]);
       }
       int []dp=new int [n];
       dp[0]=nums[0];
       dp[1]=Math.max(nums[0],nums[1]);
       for(int i=2;i<n-1;i++){
           dp[i]=Math.max(dp[i-1],dp[i-2]+nums[i]);
       }
       int res1=dp[n-2];
       dp[0]=0;
       dp[1]=nums[1];
       dp[2]=Math.max(nums[1],nums[2]);
       for(int i=3;i<n;i++){
           dp[i]=Math.max(dp[i-1],dp[i-2]+nums[i]);
       }
       int res2=dp[n-1];
       return Math.max(res1,res2);
    }
}