动态规划算法的一个变形是备忘錄方法备忘录方法也用一个表格来保存已解决的子问题的答案,在下次需要解决此问题时只要简单地查看该子问题的解答,而不必重噺计算与动态规划算法不同的是,备忘录方法的递归方式是自顶向下的而动态规划算法则是自底向上递归的。因此备忘录方法的控淛结构与直接递归方法的控制结构相同,区别在于备忘录方法为每个解过的子问题建立了备忘录以备需要时查看避免了相同子问题的重複求解。
以求斐波那契数列为例斐波那契数列,每个数都等于前两个数字之和:
下面的程序用flag数组记录哪些项已经计算过了用 ans数组存儲这些项的具体值。
下面程序的运行环境为DEV-C++
//未优化的求斐波那契数列的程序
//备忘录方法优化后的求斐波那契数列的程序