[740] Delete and Earn

奇怪，無法把它推論到house robber上！還想說是不是要三個數字group在一起判斷

我是不是天選之人～專門看不懂DP？ T—T

明明他們就是一模一樣的題目><

選max 跟算total 可以合在一個loop裡，只是hash 就必須先開很大，

看喜歡哪一種XD

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

int rob(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 deleteAndEarn(int* nums, int numsSize){

int max=0;

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

if (nums[i]>max)

max= nums[i];

int *hash=calloc (max+1, sizeof(int));

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

hash[nums[i]]+=nums[i];

return rob(hash, max+1);

}