采纳答案成功!
向帮助你的同学说点啥吧!感谢那些助人为乐的人
老师好! 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])后面才是最大值啊。
因为 偷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] 的时候,已经包含了:)
继续加油!:)
老师好,能否只考虑这两个子问题,考虑偷0+f[2…n-1]和考虑偷1+f[3…n-1]。因为他们都比后面大(如果数组里都是是正数)。
是的!可以。可以参考这里:http://coding.imooc.com/learn/questiondetail/13951.html 继续加油!:)
谢谢老师,您回复很快,很负责!!
登录后可查看更多问答,登录/注册
课程配套大量BAT面试真题,高频算法题解析,强化训练
1.1k 13
1.2k 12
684 11
1.5k 10
1.2k 10