[213] House Robber II

結果想的太複雜Orz 把自己整死Orz

原來變成circle 只要考慮從 第一間到倒數第二間  跟第二間到最後一間

這樣就可以了!!!

#define MAX(A,B) ((A>B)?(A):(B))

int robOneWay(int* nums, int numsSize){

if (numsSize<2)

return nums[0];

int *money=calloc(numsSize,sizeof(int));

money[0]=nums[0];

money[1]=MAX(nums[0],nums[1]);

for (int i=2;i<numsSize;i++)

money[i]= MAX(money[i-1] ,nums[i]+money[i-2] );

return MAX(money[numsSize-1],money[numsSize-2]);

}

int rob(int* nums, int numsSize){

if (numsSize==1)

return nums[0];

int money1 = robOneWay(nums,numsSize-1);

int money2 = robOneWay(nums+1,numsSize-1);

return MAX(money1,money2);

}