动态规划练习

Question

我一直在努力通过一个动态编程练习，但我似乎无法理解它。我将在这里写这个问题，并明确说明我不理解的问题的解决方案。

给出了两个序列u1,u2,...,un和d1,d2,...,dm，以及由正整数C=[cij]构造的维数n x m矩阵。K对((ui1, dj1),(ui2,dj2),...,(uik,djk))的列表据说是不相交的，如果是i1 < 12 <..< ik和j1 < j2 <...< jk.“列表的兼容性”被认为是它所组成的对的和的兼容性，即Ci1j1 + Ci2j2 + ... + Cikjk。

例如:考虑矩阵C = [Cij]，所以Cij = squared(i + j)。让我成为i = 1, 2, 3, j = 1, 2, 3, 4和k = 2。两个非相交对的列表是这些((u1, d2),(u3, d3))，具有9 + 36 = 45、((u2, d2),(u3, d4))、16 + 49 = 65,和((u1, d1),(u2, d4)),与4 + 36 = 40兼容的兼容性。一些非相交的列表如下：((u2, d2),(u3, d1)),((u1, d4),(u3, d3)),((u3, d2),(u2, d3))

解决方案：

M(i，j，t) =从ui，.，un和dj，...dm取的t个非相交对的最大成本

递推方程：

M(i, j, t) = max {M(i + 1, j + 1, t − 1) + c(i, j), M(i, j + 1, t),M(i + 1, j, t).}

• M(i, j, 0) = 0
• M(i, j, t) = −∞, if t > min{n − i + 1, m − j + 1}
• M(i, j, t) = 0, if i > n or j > m

最近的情况不是很好，为什么我们将−∞指定为M(i, j, t) (当t > min{n − i + 1, m − j + 1} )，而指定为0(当i > n或j > m )

解为M(1，1，k)。

Answer 1

M(i, j, t) = max {M(i + 1, j + 1, t − 1) + c(i, j), M(i, j + 1, t),M(i + 1, j, t).}
           = max
             {
                 M(i+1, j+1, t-1) + c(i, j), <- we know the maximum cost of t-1 
                                                non-intersecting pairs taken from
                                                i+1,...,n and j+1,...,m to which
                                                we prepend the pair (i, j).
                 M(i, j+1, t), <- keep it at t elements and don't prepend anything,
                                  and take the one containing elements from
                                  i,...,n and j+1,...,m
                 M(i+1, j, t) <- same, but take elements from i+1,...,n and j,...,m
             }

这涵盖了所有情况:要么我们抢占当前元素并将长度增加1，要么我们不增加长度并最大限度地利用这个(缺乏)操作所带来的可能性。您可能会问：“但是M(i+1,j+1,t)呢?这也是一个有效的可能性。”是的，但它包含在另外两种情况中：M(i+1,j,t)将检查M(i+1,j+1,t)并在需要时返回它。你可以自己把它加到重复中，这不会是错的，只是多余。

当t> min{n−∞i+ 1，m−j+ 1}时，为什么给M(i，j，t)赋值？

因为在这种情况下你无法找到解决方案。在步骤i中，您只能从第一个序列中选择n - i + 1元素(因为您已经选择了i)。j也一样。如果是t > min{n - i + 1, m - j + 1}，那么您将无法从其中一个列表中选择所需的元素数，并将其标记为负无穷大。

但当i>n或j>m时

这只是为了处理超出范围的错误。我不知道他们为什么选择0，为了一致性，我也会选择负无穷大，或者只是通过在实现中添加条件来避免它(如果i + 1 >= n然后忽略这个分支，尽管如果没有一个分支是有效的，仍然需要返回0/-无穷大)，但这并不重要。

如果您返回0，并且答案是否定的，那么您就会遇到问题。当然，对于您的问题，由于构建C的方式，我们不可能有一个负的解决方案(因为C包含数字的平方，它们总是>= 0 )。所以，在第一种情况下，可以用0代替负无穷大。

练习：，您能写一个类似的重复，但是解决方案是由M(n, m, k)给出的吗？首先用单词来定义它，然后用数学来定义它。