DP问题有没有一个学习路径？

Question

动态规划看得有点晕晕乎乎的，看了很多，不是太理解，都是似懂非懂。 请问波波老师学习动态规划有没有一个好的学习路径？ 有没有推荐的文章或者书籍等？由浅入深的那种。

Answer 1

liuyubobobo 2020-06-17 04:10:46

这一章我认为已经给出了一个简单的路径了。简单来讲就是：

1）理解基本的搜索；

2）很多搜索由于有特殊的性质（重叠子问题，最优子结构，无后效性），可以做记忆化处理，就有了记忆化搜索；

3）其实，如果熟练掌握记忆化搜索，大多数动态规划问题已经可以处理了。但是，真正的动态规划是非递归的“填表”，这个课程中讲的所有例题应该都同时使用了记忆化搜索和动态规划的方式进行了编码。通常来讲，理解记忆化搜索更容易，从记忆化搜索过渡到动态规划难一些。

网上有很多介绍动态规划的文章。你可以搜索一下。但是，我个人的建议是，动态规划只是一个概念而已。实际如何使用动态规划解决各种问题，是非常灵活的。需要见大量动态规划的经典问题，去研究总结其中的搜索方式，状态的定义方式和编码方式，才能越来越深刻的理解。

动态规划不像某种排序算法，是一个固定的算法过程，掌握了就掌握了。

关于动态规划的经典问题，这个课程介绍的背包问题，LCS问题，LIS问题，都是经典的动态规划问题。如果，这个课程所介绍的所有的例题，你已经掌握了的话，那么其实，你已经学会了动态规划。但是，对于不同的问题，你能不能灵活使用动态规划的思想去解决，需要大量的练习。

这里有一个面试常考的动态规划问题总结：https://www.geeksforgeeks.org/top-20-dynamic-programming-interview-questions/ 

其中的大部分问题在 Leetcode 上都有相同或者相似的问题可以练习。在 Leetcode 上也包含大量人写的题解，可以参考。

之前有一个北美的算法交流群的同学，总结过这些问题在 Leetcode 上对应的题号，可以参考：

这里的题目标题列的是英文，但是在力扣中文版，题号是完全一致的。

另外，如果不使用这个列表，直接在 Leetcode 的题库中，找动态规划的问题，一道一道去做，不断去总结，慢慢就有感觉了。力扣上的动态规划问题可以参考这里：https://leetcode-cn.com/tag/dynamic-programming/

可以按照难度排序，一点一点练习。

加油！：）

• 提问者 sunsky_li #1

  波波老师太厉害了，总结得很到位，基本的 DP 思想还是懂，不过缺少练习，动态转移方程不太好列，下面就准备多练练，非常感谢！