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

Idea

此题与第一题类似 将情况拆分成为不选第一号 和不选最后一号房子的两种情况即可

Code

  1. class Solution {
  2.     public  int rob(int[] nums) {
  3.         int size=nums.length;
  4.         int[] dp=new int[size];
  5.         int[] bp=new int[size];
  6.         if(size==0)
  7.             return 0;
  8.         if(size==1)
  9.             return nums[0];
  10.         if(size==2)
  11.             return Math.max(nums[0], nums[1]);
  12.         if(size==3)
  13.             return Math.max(nums[0], Math.max(nums[1], nums[2]));
  14.         //不偷最后一个房子
  15.         dp[0]=nums[0];
  16.         dp[1]=Math.max(nums[0], nums[1]);
  17.         for(int i=2;i<size-1;i++)
  18.         {
  19.             dp[i]=Math.max(dp[i-2]+nums[i], dp[i-1]);
  20.         }
  21.         //不偷第一个房子
  22.         bp[0]=0;
  23.         bp[1]=nums[1];
  24.         for(int i=2;i<size;i++)
  25.         {
  26.             bp[i]=Math.max(bp[i-2]+nums[i], bp[i-1]);
  27.         }
  28.         return Math.max(dp[size-2], bp[size-1]);
  29.     }
  30. }