algorithm - 动态规划练习

Question

我一直在努力进行动态编程练习，但似乎无法掌握它。我将在这里写下问题及其解决方案，并明确说明我不明白的内容。

我们有 2 个序列 u1,u2,...,un和d1,d2,...,dm和维度矩阵 n x m由正整数组成 C=[cij] 。 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 。 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}但当 i > n 时为 0或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)并在需要时返回。您可以自己将其添加到重复中，这不会是错误的，只是多余的。

why do we assign −∞ to M(i, j, t) when t > min{n − i + 1, m − j + 1}

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

but 0 when i > n or j > m

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

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

练习:你能写出一个类似的递归式，但其解由M(n, m, k)给出吗？首先用文字来定义它，然后用数学来定义它。