Chapter-5 DynamicProgramming 第5章 动态规划
Last updated
Last updated
LinearDP 线性动态规划
BagDP 背包问题
RegionalDP 区域动态规划
TreeDP 树形动态规划
动态规划（Dynamic Programming）是运筹学（线性规划、网络流也属于运筹学）中的一个问题分支，在查找有很多重叠子问题的情况的最优解时有效。它将问题重新组合成子问题。为了避免多次解决这些子问题（带来巨大的时间复杂度开销），它们的结果都逐渐被计算并被保存，从简单的问题直到整个问题都被解决。因此，动态规划保存递归时的结果，不会在解决同样的问题时花费时间。
动态规划只能应用于有最优子结构的问题。最优子结构的意思是局部最优解能决定全局最优解（对有些问题这个要求并不能完全满足，故有时需要引入一定的近似）。简单地说，问题能够分解成子问题来解决。
动态规划一般使用递归公式求解。递归公式也称作状态转移方程。编码中用多维数组来实现递归公式中每一步计算的结果。常见的动态规划可以划分为线性、区域、树形等。