1回答

liuyubobobo

2019-08-01

已采纳

第一个问题我无法回答你，因为你只叙述了问题，没有定义状态。一个问题，可能能定义出有后效性的状态，也能定义出无后效性的状态。

整体来说，无后效性的意思是，一个状态，怎么来的不重要，这个状态一旦确定了，它的值是一个确定的值。因为怎么来的不重要，从这个状态出发，转移到后面的状态，对后面的状态也不会产生影响。

背包问题是很好的例子。回忆一下，我们在背包问题是怎么定义状态的？

注意，我们的状态定义中，必须是，考虑将[0...i]这个范围里的物品放进容量为C的背包，价值最大。

第一次接触背包问题，一般不会想到在状态中包含容量为C这个概念的。定义的状态f(i)，就是考虑[0...i]这个范围里的物品，价值最大。

这个状态定义就是有后效性的。为什么，因为在这个状态下，从f(i)怎么转移到f(i + 1)？选不选第i+1个物品？这要看当前f(i)这个状态下选择的物品的容量。f(i)的值相同，但是对应的物品的容量不同，就导致f(i+1)不同。所以，怎么获得的这个f(i)是重要的，影响了f(i + 1)。这就叫有后效性。

回到我们的定义，一旦添加了容量c，f(i, c)是由哪些物品组成的，就不重要了。请再体会一下。

==========

对于第二个问题，sum[i][j]表示走到第i行第j列的位置的最大和。无后效性体现在怎么走来的，不重要。

如果你将状态设置成：sum[i]，表示走到第i行可以达到的最大值，是不行的，这个状态定义有后效性。

可以再体会一下。

继续加油！：）

1

8

哈哈哈蜜瓜

回复

liuyubobobo

懂了，谢谢bobo大佬！

2019-08-08

共8条回复