动态规划的状态定义

Question

老师在最后两节讲了LIS和LCS，感觉解题最关键的还是状态定义，老师能介绍下动态规划中的状态定义是如何思考的，为什么我就想不到呢？

Answer 1

liuyubobobo 2020-05-11 06:08:33

想不到是很正常的，我初学的时候也想不到：）

学习动态规划的一个重要的方法，就是多见动态规划的经典问题，多看这些问题的状态是怎么定义的，时间长了，就有经验，有感觉了。我不认为有一个固定的方法，只要掌握了这个方法，对于所有的动态规划的问题，就能瞬间找到其状态定义的方式。如果那样的话，动态规划就太简单了，也不会有那么多同学头疼了。

可以参考这里：http://coding.imooc.com/learn/questiondetail/167503.html

动态规划有很多典型的问题，应该先掌握。这个课程中介绍的 LIS，LCS，还有背包问题，其实都是这类经典的动态规划。这里有一个更大的列表，可以参考：https://www.geeksforgeeks.org/top-20-dynamic-programming-interview-questions/

加油！：）

• 提问者 慕姐8158610 #1

  谢谢老师的指导