动态规划其实就是分类讨论，只是在分类讨论后是用递归求解即可（本质上是记忆化搜索）。想到数学上的计数问题，我们分的类要覆盖到所有的情况，要满足问题中的每一个限制；分的每一类内部可以用人的脑子求出。对于动态规划问题也一样，如果是计数，状态的设计也要不重不漏，要满足问题中的每一个限制，但如果是求极值，可以重复（例如LCS问题）可以通过贪心去掉一部分状态（比如邻项交换）；分的每一类内部都需要能够递归求解，也就是可以通过之前的状态求出，这就是动态规划。
标签：有感,递归,17,2023,动态,规划 From： https://www.cnblogs.com/binyufang/p/17638823.html