图论建模与动态规划
来源：7-2 图论建模的核心：状态表达
王存俊duck
2019-09-09
老师，请问一下如何快速辨别题目是要用图论建模还是动态规划呢？就像视频中的例子leetcode 752. Open the Lock这个问题，涉及到状态转移 + 求最小值（最优值），很容易就会往动态规划的方向去想。
1回答
-
如何识别出一个问题应该使用 dp 求解？这个问题恰恰是 dp 难的地方。因为，不是那么简单的，拿到一个问题，我们就可以简单地一个性质一个性质对，然后就能确定，这个问题可以使用 dp 求解了。
在我的《玩转算法面试》中介绍的思路，基本上就是最好的确认一个问题是否可以使用 dp 求解的方式。首先，想暴力算法（通常就是回溯），之后，看是否有重叠子问题，能否记忆化搜索。通常，能够记忆化搜索了，就可以 dp 了。
但其实，这个方法没什么可操作性。因为，具体到每个问题，怎么设定状态，怎么回溯，是没有一定之规的。否则 dp 就太简单了。说实话，dp 问题可以无限难，别说普通的程序员，ACM 大神们栽在 dp 题目上都是极其正常的。如果一场比赛，有大神不会做的题目，第一可能是数学相关，第二可能就是 dp。
怎么办？我认为只能多见 dp 类问题，见多了，就有经验，有感觉了。可以参考我的公号文章《高效学习的秘密》第8条：https://mp.weixin.qq.com/s?__biz=MzU4NTIxODYwMQ==&mid=2247483836&idx=1&sn=90854aa76507281403e4dd9cd434a12b&chksm=fd8caefacafb27ec78f999fde4f1217c04c6e2ff28cf51fe511d8fa29d484d9281ff91de8c9c&token=252344042&lang=zh_CN#rd
我经常说，dp 问题，要想熟练掌握，100 道刚起步。Leetcode 上现在有 154 道标签是 dp 的 问题。都刷一遍，应该对 dp 的理解深刻很多。然后再回头看，可能你会发现，其实这些性质对解决 dp 问题，帮助不大的。真的。。。
Leetcode dp 题传送门：https://leetcode.com/tag/dynamic-programming/
最后，其实图论建模和dp不矛盾。dp是一种算法思想，图论是一种数据结构，有很多问题，是在图模型下做dp。这个课程讲哈密尔顿回路的时候，会提到这一点。经典的Prim最小生成树，和Dijkstra，都有这个意思。
加油！：）
312019-09-09
相似问题