动态规划（Dynamic Programming）

动态规划，Dynamic Programming，即DP，是一种常用的算法设计技术。此处的Programming，是指一种Tabular Method，对应DP中所谓的Memoization。

DP问题的特征：

Optimal Substructure. The optimal solution is based on optimal solutions of subproblems. The optimal solution of subproblem is based on optimal solutions of subsubproblems...
Overlapping and small Independent Subproblems. There is a subproblem graph! The number of subproblems is polynomial of input size.

Top-Down和Bottom-Up本质上一样，前者是通过递归到Bottom开始解决子问题，保存子问题的结果。但递归开销一般会比循环要大，因此Bottom-Up的性能更好！Top-Down用来建立递归，引出最后的Bottom-Up，其实不用写出Top-Down的代码。Bottom-Up不仅速度更快，内存使用也可以更少。

DP不是遍历所有可能，而是解决子问题，通过子问题的最优解决来构建更大子问题的最优解，最后解决问题。因此要求子问题最优解能够被直接使用，并且子问题重叠。所有可能的空间要比所有子问题的空间大很多...

有可能：（1）Bottom-Up计算的子问题数量更多，有些可能不会被用到；（2）最优解不止一个。

Complexity

DP算法能够把许多问题的时间复杂度降低为这种形式，即\(O(nS)\)。例如：对于Subset Sum问题，S就是Sum，对于Knapsack问题，S就是Weight...实际应用时，如果S值不是很大，这个复杂度是可以接受的。但是，这个复杂度也是指数级的！

理论上对于Input Size的衡量是bit数，n为输入个数，值占用的bit数分为\(\log{s_i}\)，此时输入bit数（input size）为\(n\cdot\log{max(s_i)}\)。\(O(nS)\)相对于input size的表达式，就是指数级的，\(2^{\log{s_i}}=s_i\)。
\(O(nS)\)有两个增长维度，既有输入的数量，也有输入具体的值。很多简单的算法，复杂度只与输入的数量有关。当复杂度与输入的值有关系时，如上一条，复杂度都将是指数级的。

-- 目录[0] --

-- 文章[15] --