关于dp无后效性分析

Question

例子1:现在有个要求需要从三张表(假设为ABC三张表)同时取数据(假设三张表结构一样，查找字段一样)，ABC总共要取15条，平均每张表取5条，假设三张表的总数据量是够的，但有可能A的数据量只有2条，那么B就要拿8条，如果B取够8条那么C只需要取5条，如果B只取了3条，那么C要取10条

例子2:leetcode120题

疑问：从例子1来看的话按顺序取值，B的取值范围需要依靠A，C的取值范围需要依靠B，那么能否看成是一种状态转移？是否有后效性？

从例子2来看无后效性体现在什么地方？

Answer 1

liuyubobobo 2019-08-01 00:42:44

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

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

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

注意，我们的状态定义中，必须是，考虑将[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

  那老师我能否理解对无后效性的定义更多是后面的状态可以对前面的状态进行多种选择？比如背包问题,f(i,c)的结果可以是f(i-1,c)也可以是v(i)+f(i-1,c-w(i))，第二个问题sum[i][j]可以是从sum[i-1][j]走过来也可以是sum[i-1][j+1]走过来，不知道这么想有没有问题

• 提问者 哈哈哈蜜瓜 #2

  另外还有一个问题是斐波那契数列，老师你给出的状态方程是f(i)=f(i-1)+f(i-2)，这里面的无后效性指的是什么？是f(i)的结果始终是不变性吗？

• liuyubobobo 回复 提问者 哈哈哈蜜瓜 #3

  你举的斐波那契恶的例子就说明了，不一定是多种选择。由于斐波那契很简单，获得结果就那么一种方式。对于斐波那切数列，无后效性同样意味着，怎么到达f(i)无所谓。但是因为对于这个问题，也只有一种到达f(i)的方式，所以，斐波那切数列体现不出来无后效性的意义。但他也没有破坏无后效性。

点开查看后面5条评论