所有的 DP 问题都可以简单得用 Recursion 的方式实现。这通常是最容易想到的思路。
问题是这种实现不够 efficient,存在 subproblem 被重复计算的情况。有两种解决这个问题的方法:
1. 很直观的,在 naive recursion 里加入 一个 save 的环境,把每个 subproblem 计算出的值存起来。这种方式也叫 Top-down approach。
2. Bottom-up approach: 上面的方法的思路是从大问题开始,计算的时候发现需要小问题的解,再立即去计算小问题,小问题计算完毕返回后利用小问题的解继续计算大问题。另一种思路是直接从小问题开始计算,利用各个小问题的结逐步计算出更大问题的解,直到最后原问题的解被计算出来。
此种思路的优点是可以不依赖递归,用 iterative approach 实现,执行效率上会快一些。但是这种方法需要对问题彻头彻尾的分析,才能够知道如何由小问题的解组成大问题的解,而且写出来的代码虽然执行效率高,不如第一种方法的代码容易理解。
Dynamic Programming (DP) 问题总结,布布扣,bubuko.com
原文:http://www.cnblogs.com/Antech/p/3779551.html