分析
分析以下例子:
房子编号: 0 1 2 3 4 5
房子收益: 4 2 8 6 1 3
目标: 偷 n 个房子获益的最大值
约束条件: 相邻房子不能同时偷
可能的操作序列:
- 0 2 4
- 0 2 5
- 0 3 5
- 1 3 5
- 1 4
小偷面对编号为 i 的房子时, 他会有两种决策:
1) 偷 (暗含着前一个房子没偷)
2) 不偷 (注意不一定暗含着前一个房子一定偷了, 如果想成前一个房子一定要偷, 这就表示偷房子的序列为间隔性的能偷的最大钱数, 这是不一定的, 比如: 3,2,2,3, 最大收益为 6, 中间隔了两个房子!)
如何做决策?
分别比较下这两种决策下的最大能偷的钱数:
1) 偷 i, 能获得收益为: maxval = num[i] + premax, 其中 premax 表示前一个房子没偷能拿到的最大钱数;
2) 不偷 i, 能获得最大收益为: premax 和前一个房子偷了能获得最大收益, 的最大值, 即 premax = max(premax, maxval), 需要注意:
前一个房子偷了能获得最大收益 为上一步的 maxval(它就是表示偷了 i, 所以需要用一个临时变量存储起来, 供下一个时步用)
可以看到这两种情况相互耦合
1) 的 premax 实际上是上一时步 2) 的 premax
2) 的 maxval 实际上是上一时步 1) 的 maxval
最后一步, 遍历结束后, 取 maxval 和 premax 的最大值
来源: https://mp.weixin.qq.com/s?__biz=MzI3NTkyMjA4NA==&mid=2247485186&idx=1&sn=4d9f3f75550e1dc032b0818a2d8cabd9&chksm=eb7c2ac9dc0ba3df898e993050cb2d0004866adf3a618047826270cad49f80ea0fb22395bf39#rd