一、从分治到动态规划
1.1 动态规划的性质
动态规划具有以下三个明显特性:
- 无后效性:如果给定某一阶段的状态,则在这一阶段以后过程的发展不受这阶段以前各段状态的影响。如果说的直白一些,就是当我们求出 $dp_i$ 的时候,我们是怎样求出来的,就不用管了,我们只需要利用 $dp_i$ 就可以了。类似于“只要上了北航,没人管你到底是从河北考上的的,还是从月球考上的,大家只认为你是一个北航学生。”
- 最优子结构:规模大的最优化问题包含规模小的最优化问题,大问题的最优解可以由小问题的最优解推出。
- 重叠子问题:子问题的解不止会被利用一次。
虽然这三个特性都被称为“动态规划”的特性,但是“无后效性”和“最优子结构”并非是动态规划的专利。对于“无后效性”,应该是所有的分治算法都具有这个特性,如果我们必须掌握子问题的求解过程,那么显然我们就没必要将大问题分治为小问题。对于“最优子结构”,虽然“最优”二字将问题划定成了“最优化算法”的范畴,但是如果扩充最优化的定义,会发现依然几乎所有分治算法都满足具有最优子结构的定义。