198.house robber中分解子问题的问题
来源：9-4 状态的定义和状态转移 House Robber
厦门黄猫编程
2020-11-09
老师好！
198.house robber中，你讲原问题是考虑偷0->n-1,我用f[0]表示，子问题如下分解：
考虑偷0+f[2…n-1]
考虑偷1+f[3…n-1]
考虑偷2+f[4…n-1]
…
f[n-1]
我觉得到考虑，偷2+f[4…n-1]这时候为什么这个子问题，不回头考虑要偷0，max（偷2+f[4…n-1]，偷0+偷2+f[4…n-1]）后面才是最大值啊。
写回答
1回答
-
因为 偷2+f[4…n-1] 就是 f[2] 呀。f[2] 表示考虑偷 [2...n-1]，自然包括 偷 2， 然后继续考虑偷 [4...n-1]
所以，你的 偷0+偷2+f[4…n-1] 在计算 偷0+f[2…n-1] 的时候，已经包含了：）
继续加油！：）
332020-11-10
相似问题