作者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/cn.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