动态规划与分治
动态规划
利用问题的解与其子问题的解之间的关系（动态规划方程），以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的解的算法
分治(Divide and Conquer)
将一个问题分为若干个子问题，将这些子问题分别求解；将求出的小规模的子问题的解合并为一个更大规模的问题的解，自底向上求出原来问题的解
核心思想：大问题—>小问题
区别：
分治：自顶向下
动态规划：自底向上
动态规划的基本步骤
- 找出最优解的性质，并刻画其结构特征
- 建立动态规划方程
- 以自底向上的方式解动态规划方程
- 根据计算最优质的时得到的信息构造最优解
Pseudocode:
dynamic-program(P)
{
for(i=1;i<=n;i++)
{
compute(solution of each Pi);//解规模为i的各子问题
use(solution of each Pi) merge(solution of each Pi+1);
//将规模为i的各子问题的解合并为规模为i+1的问题的解
}
}