关于 DP 的3个性质，以及如何确定某个问题是否可用 DP 求解

Question

Hi bobo 老师，

我在其他参考资料上看到说，若一个问题可以采用 DP 求解，则该问题一定满足3个性质：

1. 最优子结构

2. 重叠子问题

3. 无后效性

这里我有两个问题想问一下 bobo 老师：

1. 咱们课里只讲到了性质1和2，但是没有提及性质3，不知是为什么？

2. 如何在拿到一个问题时确定它是否符合这3个性质？如果不能确定的话要如何才能认定这个问题是否可以采用 DP 求解呢？

谢谢老师！

Answer 1

liuyubobobo 2019-08-22 16:27:42

1 

我个人认为，最优子结构，就是无后效性的意思；

2

如何确定一个问题可以使用 dp 求解？这个问题恰恰是 dp 难的地方。因为，不是那么简单的，拿到一个问题，我们就可以简单地一个性质一个性质对，然后就能确定，这个问题可以使用 dp 求解了。

我个人人认为，课程中介绍的思路，就是最好的确认一个问题是否可以使用 dp 求解的方式。首先，想暴力算法（通常就是回溯），之后，看是否有重叠子问题，能否记忆化搜索。通常，能够记忆化搜索了，就可以 dp 了。

但是，dp 复杂的地方，在于如何设定状态，也就是如何回溯。比如在这个问答中，我以背包问题为例，说明了状态设置的重要性：http://coding.imooc.com/learn/questiondetail/134490.html

但是，怎么能找到最适合 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/

加油！：）

• 提问者 Poplar_hills #1

  非常感谢！向一百道发起冲锋 :D