DAG上的动态规划与树形DP这两个词看上去很高大上，但实则就是记忆化搜索，而记忆化搜索其实就是DP的本质。当选择一个需要用全局变量来参与描述状态的方式时，就只能用常规搜索。但当状态可以完全被几个非全局参数确定性的描述时，就可以用记忆化搜索，记忆化搜索可以通过存储答案并直接提取来大大减少时间复杂度，可见重复状态越多、则记忆化搜索所带来的优化就越大，而当状态完全不重复时，记忆化搜索就退化成了最朴素的搜索，且无法使用全局变量的限制还凭空增加了思维复杂度，显然不划算。因此，我们只有会使用有意义的记忆化搜索，即因重复状态较多而可以带来较大优化的记忆化搜索。特别的，我们为这种记忆化搜索起一个好听的名字，这便是动态规划。
动态规划的核心在于用几个参数完全且确定地刻画某一个状态，然后依照状态间的关系进行记忆化搜索，特别的，因为动态规划的状态完全有几个参数表示，DP的状态因而可以被写在一个表格、一个长方体、或任何n维体上，且状态间的关系具有单调性，这使得我们可以按照一个较为简单的规则而非按照搜索的自然顺序来进行计算，且可以保证虽然并未按搜索的自然顺序来计算，但任何状态在他被用到之前都一定已经算好了，也就是说保证了结果的不变性。这种简单的规则通常是按行按列的填表法，或者其他能被几个循环简单描述的填表法，总之这种简单的规则太过于普遍的能够出现，且可以转递归为循环省去了栈空间，因而被广泛应用，甚至倒反天罡让初学者误以为这才是DP的自然形态，使得初学者无法意识到DP的本质因而极难真正理解DP。尽管如此，递推式DP确实好用，因而我们下文在DAG上的DP与树形DP这两个传统记搜领域以外，都将全部采用递推式DP来分析，不过学习者要始终记得DP的本质及递推式DP这种方式的本质。
背包DP，其实算不上是一种DP，只是为了解决背包问题而单独画出来的一个门类，实则就是用多个参数来刻画状态并递推式地进行状态转移。
区间DP，其实只是一种特殊的二维DP，两个维度分别表示要描述的区间的左右端点，DP值则是描述该区间某性质的一个量值
当DP函数的取值只有0和1时，或其他取值范围很小的时候，我们要时刻记住DP的取值实则就是免费赠与我们的一个维度，即二维DP实则可以描述一个三维逻辑空间中的状态，因为两个参数加一个DP值正好三维，可二维DP的时间复杂度却只取决于两个参数，不取决于DP值。因而DP值可以理解为免费额度，从占小便宜的角度来想，我们要尽可能的利用免费额度多占便宜，真要花自己钱的时候则要尽量节省。因此当DP函数的取值只有0和1时，或其他取值范围很小的时候，我们就要将DP值和某一个取值范围很大的维度的参数相调换，这样就几乎可以减去一个维度的时间复杂度，从而实现类似立方时间复杂度的算法化简为平方时间复杂度一类的操作
标签：总结,状态,取值,复杂度,搜索,记忆,动态,规划,DP From： https://www.cnblogs.com/gongkai/p/18366409