作者shanlin1117 (小山)
看板java
標題[問題] 一個陣列運算的題目
時間Wed Aug 23 09:03:34 2017
小弟剛剛收到同學問我的一個問題
假設你是一位職業的小偷，現在你鎖定了某一條街上面的房子，
打算今天晚上對這排房子下手偷竊，每一間房子都存在著不同數目的錢。
但是相鄰的兩個房子間有警報系統會直接通知警察，
所以你不能連續偷兩間相鄰的房子，例如房子依照以下排列：A, B, C, D, E
，當妳要偷B房子時，則無法偷A與C。
給定一個陣列money[n]，其中n代表有幾間房子，
而陣列中的數值代表每個房子裡面的金錢，
請設計一個函數來找到今晚能偷到最多的金錢數目。
例如給定陣列：
money[0] = 1
money[1] = 5
money[2] = 2
money[3] = 1
則身為職業的小偷會選擇偷money[1]與money[3]，而函數會回傳6 (5+1)。
目前想法
假設有A B C D E F 五間房
組合就有
1. A C E
2. A C F
3. A D F
4. B D F
5. B E
然後把每個組合的數字加總起來取最大就行了
但還沒有想到應該怎麼去下loop
不知道有沒有大大可以指點一下迷津
給提示也行QQ
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 125.227.21.55
※ 文章網址: https://webptt.com/m.aspx?n=bbs/java/M.1503450216.A.9CC.html
1F：→ jej: 先用線性規劃找出最佳解的數學矩陣 用程式來算 08/23 09:52
2F：→ jej: 或者寫排列組合 全列出來後淘汰有連續的組合 再去最大的 08/23 09:54
3F：→ ssccg: f(n) = max(f(n-1), money[n-1] + f(n-2))，標準遞迴DP題? 08/23 10:36
4F：→ ssccg: 不偷最後一間↑ ↑偷最後一間(不能偷倒數第二間) 08/23 10:38