请稍等 ...
×

采纳答案成功!

向帮助你的同学说点啥吧!感谢那些助人为乐的人

198.house robber中分解子问题的问题

老师好!
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] 的时候,已经包含了:)


继续加油!:)

3 回复 有任何疑惑可以回复我~
  • 提问者 厦门黄猫编程 #1
    老师好,能否只考虑这两个子问题,考虑偷0+f[2…n-1]和考虑偷1+f[3…n-1]。因为他们都比后面大(如果数组里都是是正数)。
    回复 有任何疑惑可以回复我~ 2020-11-09 20:17:00
  • liuyubobobo 回复 提问者 厦门黄猫编程 #2
    是的!可以。可以参考这里:http://coding.imooc.com/learn/questiondetail/13951.html 继续加油!:)
    回复 有任何疑惑可以回复我~ 2020-11-10 11:29:57
  • 提问者 厦门黄猫编程 回复 liuyubobobo #3
    谢谢老师,您回复很快,很负责!!
    回复 有任何疑惑可以回复我~ 2020-11-10 11:55:39
问题已解决,确定采纳
还有疑问,暂不采纳
意见反馈 帮助中心 APP下载
官方微信