动态规划的“后效性”：一文搞懂

动态规划的“后效性”

引入

动态规划问题必须满足两个基本条件：最优子结构、无后效性。

最优子结构 是说问题的最优解可以包含子问题的最优解，也就是可以从子问题的最优解不断推导出整个问题的最优解。

后效性 的百度百科定义是某阶段的状态一旦确定，则此后过程的演变不再受此前各种状态及决策的影响。通俗地说，就是当前阶段的决策不会受到过去历史路径的影响。这里的是说：我们当前阶段的决策还是需要用到过去的一些状态的（比如打家劫舍的当前房子偷与否取决于前一个房子是否被偷），但是并不关心是如何到那个旧状态的，我们只关注那个状态的值。

当前决策可以依赖过去的状态值，但不能依赖到达这些状态的具体路径。

例题

考虑下面这道经典的题目。

198. 打家劫舍

我们要偷房屋，但是不能偷连续的房屋。做法是设计一个一维dp数组，每个房屋都是这个数组中的一个位置，dp[i]的含义就是小偷偷到第i个房屋时，能偷的最大值。那么状态转移方程就是dp[i] = Math.max(dp[i-1],dp[i-2]+nums[i])；当前阶段的决策由上一间房屋是否偷影响，但是这个影响并不是历史路径，也就是我们只关心上一间房屋记录的状态（偷的最大值），并不关心它是如何到达这里的。这就是无后效性。

破坏无后效性

我们修改一下题目条件。

变为小偷不能连续地偷房屋，但是也有一个偷的上限，最多只能偷K间。

如果是这样的条件的话，还使用原来的dp数组就会出现状态记录不够的情况，从而破坏了无后效性的性质。当前阶段的决策不仅要被前面一些状态影响，还要额外地考虑当前偷了多少间房屋了（历史的偷窃次数会影响未来的决策）。如何再次让他满足无后效性呢？只要将dp扩展为

dp[i][count] = 偷到第i间房屋，已偷count间房屋的最大价值

就可以使得它再次满足无后效性了。

总结

动态规划的核心思想是将复杂问题分解为子问题，通过存储子问题的最优解来避免重复计算。 无后效性确保了我们可以基于当前状态做出最优决策，而不需要回溯历史路径。这就像下棋时，我们只需要知道当前棋局状态就能决定下一步最优走法，而不需要知道棋局是如何演变到当前状态的。 当问题的状态定义不足以支持无后效性时，我们需要扩展状态维度，将影响未来决策的所有必要信息都编码到状态中。这样，状态的定义包含了做出最优决策所需的全部信息，使得未来的最优决策只依赖于状态值，而不依赖于历史路径。