老师我有个地方有点想不通

Question

之前的买卖股票和打劫的题目算是背包问题吗，感觉有点像又始终联系不起来，如果不是，区别在哪里呢，如果是，那么是什么样的背包问题呢，怎么分析才能看出来？还有，动态规划的问题是不是都是背包问题的变形呢？

Answer 1

liuyubobobo 2021-10-12 03:45:56

不是，就是动态规划。

不是所有的动态规划都是背包问题的变形。如果是的话，动态规划也太简单了。

我个人也并不建议用这种方式去学习动态规划，非要把每一个问题扔进一个典型例题的类别中。当然，在初期，能帮助你理解，固然好。但是解决动态规划问题的方式，并非是首先把一个问题一个一个往典型例题里套，套进去了自然代码就出来了。不是的。即使你看到有的问题的题解，发布者一本正经地说，这就是一个背包问题的变种，但实际上，在解决这个问题的时候，他的头脑里反映的不一定是背包问题。而是事后总结，总结出来了。

那么解决动态规划问题的时候，头脑里是什么？就是：这个问题可不可以搜索得到？怎么搜？这样搜是不是有大量的重叠子问题，所以可以用记忆化的方式优化？这就是记忆化搜索的代码。

等到熟练到一定程度，自然而然就会想到，是不是可以通过基本情况一步一步类推出来？也就能直接写出 dp 代码了。

如果你已经理解了那个问题，我不建议你继续和那个问题较劲了。非要从一个问题里分析出一个什么思路经验，很多时候是不靠谱的。思路和经验是靠一堆问题，大量的实践，分析总结出来的，而不是靠一个问题分析出来的。

可以参考我的公众号文章，搜索 dp 的一小段文字：https://mp.weixin.qq.com/s?__biz=MzU4NTIxODYwMQ==&mid=2247487758&idx=1&sn=60489a94e731844df6c6b6f0d1307d28&chksm=fd8cbe48cafb375e71444b94aaed59585e14821625967a90b1d6fc6dbfd9301eaf815e0aee5a&token=1140963998&lang=zh_CN#rd

继续加油！：）

• 提问者 湿地车手 #1

  哦，这下理解了，其实我之前就是按照记忆化搜索思路直接去做dp的，只是看到这节课以后突然有点疑惑，谢谢bobo老师！！！！