动态规划

Question

动态规划里常说的无后效性怎么理解？有后效又是什么问题？

Answer 1

liuyubobobo 2020-10-21 18:18:39

第八章回溯法介绍的问题，都是有后效性的问题。

比如排列问题，我们搜索到了第 6 位应该排哪个数字。但此时，第 6 位排哪个数字，不足以确定当前找到的前六位的排列是怎样的。这就叫有后效性。前面的搜索具体是怎样的，会影响当前的搜索。

这一章介绍的所有动态规划的问题，相应都是无后效性的。比如对于斐波那切数列来说，f(6) 是多少，是固定的，没有不同的 f(6) 的值，来影响后续的 f(7) 或者 f(8) 的计算。

说实话，我个人认为，这个概念本身，并没有那么重要。没有人会在面试中问你什么是无后效性；我也不认为你对“无后效性”这个概念说得一清二楚之后，对于所有的动态规划问题，你就能很轻松的做出来。反而我个人的体会是：你可能先是慢慢地能用动态规划的思想解决一些问题了之后，才开始真正理解“无后效性”这个概念。可以参考我的公众号文章：https://mp.weixin.qq.com/s?__biz=MzU4NTIxODYwMQ==&mid=2247485746&idx=1&sn=3f4cf85a368ab792fc424f2086a508dc&chksm=fd8ca674cafb2f6211147a8f524bbc8b805caeb369c6298b18bd7dadc5a0d368563992853dce&token=1104391584&lang=zh_CN#rd

相较这个概念而言，我认为理解记忆化搜索，是突破动态规划的关键。这也是为什么我在这一章，所有的代码都会既写记忆化搜索的代码，又写动态规划的原因。我建议你跟着这一章学习的过程中，对每一个问题都去思考：该怎么搜索？这样搜索怎样可以做记忆化？这样搜索是如何定义状态和状态转移的？最后怎么得到了动态规划的代码？

尤其是这一章最后的背包问题，思考一下：如果使用回溯的方法，怎么求解背包问题？而使用动态规划的方式，又是怎么求解的？他们的核心区别是什么？为什么动态规划的方式性能更好？（实际是状态的定义完全不同）。

对这一章的每一个问题都这样总结，相信你对动态规划的理解能提升一大截。

加油！：）

• 提问者 厦门黄猫编程 #1

  谢谢老师！