引言
Those who cannot remember the past are condemned to repeat it.
动态规划算法的核心是记住已经求过的解,记住求解的方式有两种:自顶向下的备忘录法和自底向上。
小试牛刀-杠条切割问题
上图节选自算法导论。
经典朴素递归
|
|
自顶向下递归实现的CutRod效率很差,原因在于CutRod反复地用相同的参数值对自身进行递归调用,即它反复求解相同的子问题。而且由于递归调用次数太多会栈溢出。
动态规划-自顶向下
|
|
此方法仍按自然的递归形式编写过程,但过程会保存每个子问题的解。当需要一个子问题的解时,过程首先检查是否已经保存过此解。如果是,则直接返回保存的值,从而节省了计算时间;否则,按通常方式计算这个子问题。
动态规划-自底向上
|
|
恰当定义子问题“规模”的概念,使得任何子问题的求解都只依赖于“更小的”子问题的求解。因此,我们可以将子问题按照规模顺序,由小至大顺序进行求解。当求解某个子问题时,它所依赖的那些更小的子问题都已求解完毕,结果已经保存。每个子问题只需求解一次,当我们求解它时,它的所有前提子问题都已求解完成。
由于没有频繁的递归函数调用的开销,自底向上方法的时间复杂度函数通常具有更小的系数。