这是一套个人认为非常漂亮的DP框架，并且得到了清北浙交、全球一线科技大厂SDE、前ACM世界总决赛选手的高度评价，掌握这套框架后可以帮助你通过五道题目掌握DP的出题技巧，根据个人有限的经验来看，整个DP框架可以覆盖力扣90%以上的DP问题~
我们以 有序 为线索，将DP分类以下五类，同时也通过这五种类型DP对应的5道枚举题目来引出动态规划的框架
- 无序：组合
- 定序：选择：元素点的选择 | 分割：分割点的选择
- 有序：排列
- 反序：博弈
这套DP框架对于新手是易学，易用，优雅，简洁的，大家可以在看完这篇文章后尝试去出一些DP问题，相信即便你是刚刷过斐波那契的小白，也能随心所欲地进行DP出题~
首先我对DP的理解是在DAG上进行搜索，DAG最核心的就是要分析重叠子问题的重叠是哪里来的？当枚举的状态空间过大，同时定义状态空间过小时，势必会产生重叠性的搜索，因为这些庞大的搜索空间的结果必然要落在我们定义的有限的状态上，就会产生所谓的重叠。
那什么是最庞大的状态空间呢？学过时间复杂度的同学都知道，排列时间复杂度n!以及组合时间复杂度2^n就是最大的时间复杂度，这个时间复杂度是计算机不能承受的，那么它们对应的全排列和全组合问题其实就会产生重叠性。
比如说我们对nums数组[1,2,3,4,5]求全组合，如果我们把dp[i]定义为nums.slice(i,nums.length)形成的所有组合，我们就会发现对于dp[0]，不论选择第0个数，还是不选第0个数，剩余要做的事情都是相同的，都是dp[1]，这个相同就是重叠性的来源，那为何我们不做DP而用回溯呢？仅仅是因为DP的好处是在用空间换时间，但是这里我们会发现用空间换不了时间，因为存储dp[1]需要大量的空间，并且我们需要枚举dp[1]中存在2^(n-1)个解才能把dp[0]求出来，既然空间换不了时间，那么做记忆化就没有意义了~
其实用空间换时间，从不同大小视角去看，就会发现不同的意义，微观下的空间换时间可以说动态规划的技巧，中观的空间换时间熟悉前端框架的小伙伴可能知道数据响应式的DAG的computed属性和普通函数的区别就是computed是带缓存的，宏观上的空间换时间就是缓存，但是这会带来数据不一致的问题~
我们再次回到我们要讨论的内容，如此可见全组合问题不能用动态规划主要是它是求所有解，那么是不是只要它不是求所有解那就可以用动态规划解了呢？答案当然是肯定的
比如说组合DP我们试图不求全部的值，仅求单值的话那肯定可以用动态规划，这时候我们会发现如果是求能形成的组合个数那就直接是2^n了，这样数学就能解了，就无需动态规划了，所以我们还需要让情况变得复杂一些，比如说
- 求nums数组中是否存在元素之和等于target → boolean
- 求nums数组中元素之和等于target且要求挑选出最多的元素个数 → int
我们会发现一件事情，就是我们并不清晰到底能添加哪些限制，那这里我就给大家简单总结了一下常见的要素，我们发现组合DP能够调整的要素只有两个，一个是每个数字可以选多少次，第二个是这些数字凑成的目标=、<、>、≈某个目标，并且可以要求符合多个目标~
其实这是和现实生活完全对应的，小于限制就是资源的限制、大于限制就是产出的限制、我们人生也处处是限制，比如说情人节，我们都希望在一定的预算下购买的礼物，至少得让女朋友满意度大于某值，求所有购买礼物的方案数量，这就是两种限制同时存在的情况。
根据这两种限制相信大家肯定能出无数道的DP问题了，毕竟我们生活在如此受限的现实世界中，大家都不容易~
最后我们来谈谈所有DP的目标求解问题，其实这个倒是非常简单的，对应到DAG图上一般都是最短路径、最长路径、路径个数，这个翻译成语义就是最小方案数、最大方案数、方案总数，大家可以尝试去总结~
注意组合DP是完全无序的，所以在组合DP的基础上我们引入有序性就成为定序DP，我们先来谈谈选择DP，选择DP是可以完全继承下来组合DP的限制并且在其基础上添加了三种限制，分别是状态限制、连接限制、结构限制，所以我们现在能用的要素又多了三种。
状态限制指的是组合DP每个元素点选或不选的2^n个状态空间，那么选择DP就变成了m^n个状态空间，也就是每个元素点可以变成任意模式，比方说股票买卖问题中每个数字我们可以改变正负号或者置为0，比如说每个元素位我们可以涂成不同的颜色，比如说每个元素位置可以放上不同的。
连接限制指的是选择出来的元素构成某种规律的序列，比如说要求选择的序列单调递增，要求选择的序列先增后递，要求选择的序列的元素不相邻，要求选中的序列元素最大值和最小值之差不得超过一个数等，比如说要求颜色A只能与颜色B相邻，其实只要大家能想到的，都是动态规划问题。因为原始的状态空间是m^n是非常大的，我们定义的状态空间远远小于原始的状态空间，那么原始枚举的状态空间会落到定义的状态空间上，一定有重叠性可以做动态规划的。
结构限制其实也是有序带来的，广义的有序当然包括结构了，所以线、树、图的引入又会让选择DP变得更加复杂，比如树型打家劫舍，矩阵连接限制又会形成所谓的插头DP等，这又构成了复杂性的来源。
其实我们发现上述问题都可以用枚举解决，并且枚举的状态空间也非常大，其实只要大家能想到的枚举，我们就一定能发现它的重叠性，并把它做成动态规划~
经过组合DP以及选择DP的学习，我们手上拥有了次数限制、数量限制、状态限制、连接限制、结构限制这五张牌+目标求解一张牌，有这么多牌是不是DP可以随便出了呢，是不是恍然大悟了呢，是不是觉得DP如此简单呢？
其实入门就是这么简单，但是因为要素足够多，而且要素经过组合加工之后会变得非常非常复杂，不过新手朋友们认识到本质就可以了，表象是无穷无尽的。
毕竟熊彼得说过，创新是要素的组合，把大家学会要素就可以了，要素组合相信大部分同学都是可以组合的，小白可以尝试用同时上述五种限制以及目标求解结合实际问题出一道DP问题，如果能够加以解决的话，相信会大有收获，可以说力扣动态规划200题你可以秒解了~
至于分割DP、排列DP、博弈DP就后面有时间再写了
最后新手朋友可以看一下下面这个免费课程，这个课程会通过四道题目快速帮助你建立一套相对完备的算法框架，通过四道题目核心题目的讲解达到200道题目的水平，看不懂这个帖子的同学可以先补一下这个课程再看效果会非常绝佳，并且配备了非常详细视频、讲义以及多语言支持，文档的多语言来自武大、浙大、华科、华东师范、西交、东北大学同学，非常感谢他们的付出~
最后有其它领域的大佬想要制作出优雅、简洁、易懂的教学内容来帮助初学者更好学习可以参考一下本人写的分类讲义，我可以帮忙做概念系统的建构，本人在分类上的见解相对而言是比较深刻的，主要依赖的原理是辩证法以及熊彼得的创新是要素的组合这两条铁律，这件事情迫在眉睫，已经到了不得不做的地步了，归根到底文明的进展依赖于社会总体学习效率的提高~
