[198] House Robber （20221125 更新）

給一個array代表每間房子的$$數目
若相鄰的房子都被搶了會引起警報系統報警
所以只能間隔著搶 (好爛的警報系統XD)
請找出搶劫（還是偷竊啊其實一樣吧總之題目是用rob, 雖然這根本不是重點, 現在是在考 DP不是在考英文啊啊啊~~~~~~）並且不引發警報系統的前提之下可以搶到多少錢（真是教壞囝仔大小啊~）（是說有人知道囝這個字怎麼唸嗎?! 給你三秒鐘～～～～一～～～二～～～三～～～唸簡！！！這真是太神奇了寫程式長知識～寫程式的小孩不會變壞喔啾咪 >. ^ ）（只會變得不太正常）（是否不應該繼續離題）

感謝 這個作者 （leetcode網站）的說明
他寫的好清楚啊啊啊啊滾向東又滾向西
XX公司想要hire的就是這種人吧
我去XX公司掃樓梯就好了我應徵什麼RD呢～（哭）

每一個item都有 搶 跟 不搶 的選項（根本就不應該有搶的選項啊啊啊教壞囝仔大小）
搶的話, yes 會等於 這間的錢 加上 前一間不搶的錢 (一路搶下來)
不搶的話, no 會等於 前一間搶 或是 前一間不搶 取大的那一個
一路算下去, 再回傳yes 或 no 的最大值.
其中tmp 是用來紀錄 "前一次的yes" (或是拿來紀錄no也可以)
沒用tmp存的話, 它會算成這一次的yes (或no)
就是這樣了！（擊掌）

House Robber
#define max(a, b) ((a)>(b)?(a):(b))

int rob(int* nums, int numsSize) {
    int yes=0,no =0,i;
    for(i=0;i<numsSize;i++)
    {
        int tmp = yes;
        yes = nums[i] + no;
        no = max(tmp,no);
    }
    return max(yes,no);
}

20221125 更新

感覺我快要參透DP了 ！！！

#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]);

}