|
|
动态规划算法的备忘录方法和回溯法有什么区别？
感觉没很大区别，都是自顶向下搜索的
关注者
38
被浏览
25,120
6 个回答
特意去查了啥叫备忘录算法啥叫回溯法…感觉上是这样的
动态规划本身是有若干种实现方式的，可以顺推，也就是常见的for循环实现，可以逆推，逆推也可以for循环实现，可以记忆化搜索，应该就是所谓的动态规划的回溯法吧，可以用的时候用哪个记忆化搜哪个，就是备忘录算法吧。三者的区别是，动态规划涵盖了各种动态规划的实现，回溯法本身就是一种实现方式，备忘录只是不需要一开始全搞出来，而是用哪个算哪个。
不严格的说：
注意到回溯会"回到"访问过的状态。当然只是恢复部分状态而已，人不可能踏入同一条河流两次。总体上来看，"回到"的那个状态也是个新状态。
动态规划就是填好初始状态的答案和转换方法。然后知道答案的范围越来越大，直到知道关心的原问题的答案。
备忘录法只是实现动态规划的一种方法。动态规划最难的是搞定关注的问题是啥，转换方程和初始状态的解。