老师我有个地方有点想不通
来源：9-7 面试中的0-1背包问题 Partition Equal Subset Sum
湿地车手
2021-10-12
之前的买卖股票和打劫的题目算是背包问题吗，感觉有点像又始终联系不起来，如果不是，区别在哪里呢，如果是，那么是什么样的背包问题呢，怎么分析才能看出来？还有，动态规划的问题是不是都是背包问题的变形呢？
1回答
-
liuyubobobo
2021-10-12
不是，就是动态规划。
不是所有的动态规划都是背包问题的变形。如果是的话，动态规划也太简单了。
我个人也并不建议用这种方式去学习动态规划，非要把每一个问题扔进一个典型例题的类别中。当然，在初期，能帮助你理解，固然好。但是解决动态规划问题的方式，并非是首先把一个问题一个一个往典型例题里套，套进去了自然代码就出来了。不是的。即使你看到有的问题的题解，发布者一本正经地说，这就是一个背包问题的变种，但实际上，在解决这个问题的时候，他的头脑里反映的不一定是背包问题。而是事后总结，总结出来了。
那么解决动态规划问题的时候，头脑里是什么？就是：这个问题可不可以搜索得到？怎么搜？这样搜是不是有大量的重叠子问题，所以可以用记忆化的方式优化？这就是记忆化搜索的代码。
等到熟练到一定程度，自然而然就会想到，是不是可以通过基本情况一步一步类推出来？也就能直接写出 dp 代码了。
如果你已经理解了那个问题，我不建议你继续和那个问题较劲了。非要从一个问题里分析出一个什么思路经验，很多时候是不靠谱的。思路和经验是靠一堆问题，大量的实践，分析总结出来的，而不是靠一个问题分析出来的。
可以参考我的公众号文章，搜索 dp 的一小段文字：https://mp.weixin.qq.com/s?__biz=MzU4NTIxODYwMQ==&mid=2247487758&idx=1&sn=60489a94e731844df6c6b6f0d1307d28&chksm=fd8cbe48cafb375e71444b94aaed59585e14821625967a90b1d6fc6dbfd9301eaf815e0aee5a&token=1140963998&lang=zh_CN#rd
继续加油！：）
012021-10-12
相似问题