跳转至

动态规划 无后效性

最后再谈谈「无后效性」

「无后效性」是我多次提到的一个「动态规划」中非常重要的概念,在我看来,理解这个概念无比重要。很遗憾,《算法导论》上没有讲到「无后效性」。我找了一本在「豆瓣」目前豆瓣上评分为 9.2 的书 《算法竞赛进阶指南》,这本书和《算法导论》《算法 4》和 liuyubobobo 老师的算法课程一样,在我学习算法与数据结构的道路上,都发挥了巨大的作用。

李煜东著《算法竞赛进阶指南》,摘录如下:

为了保证计算子问题能够按照顺序、不重复地进行,动态规划要求已经求解的子问题不受后续阶段的影响。这个条件也被叫做「无后效性」。换言之,动态规划对状态空间的遍历构成一张有向无环图,遍历就是该有向无环图的一个拓扑序。有向无环图中的节点对应问题中的「状态」,图中的边则对应状态之间的「转移」,转移的选取就是动态规划中的「决策」。

我的解释:

  • 「有向无环图」「拓扑序」表示了每一个子问题只求解一次,以后求解问题的过程不会修改以前求解的子问题的结果;
  • 换句话说:如果之前的阶段求解的子问题的结果包含了一些不确定的信息,导致了后面的阶段求解的子问题无法得到,或者很难得到,这叫「有后效性」,我们在当前这个问题第 1 次拆分的子问题就是「有后效性」的(大家可以再翻到上面再看看);
  • 解决「有后效性」的办法是固定住需要分类讨论的地方,记录下更多的结果。在代码层面上表现为:
    • 状态数组增加维度,例如:「力扣」的股票系列问题;
    • 把状态定义得更细致、准确,例如:前天推送的第 124 题:状态定义只解决路径来自左右子树的其中一个子树。

总结

「动态规划」的解法,我们先告诉大家,理解题意非常重要。其次,我们在做「动态规划」的问题的时候,需要经常思考 为什么想到需要这样定义状态。

https://leetcode.cn/problems/maximum-subarray/solutions/9058/dong-tai-gui-hua-fen-zhi-fa-python-dai-ma-java-dai/