动态规划练习

Question

我一直在努力完成一个动态规划练习，但我似乎无法掌握它。我会在这里写下问题及其解决方案，明确说明我不明白的地方。

我们给定了 2 个序列 u1,u2,...,un 和 d1,d2,...,dm 以及维度为 n x m built 的正整数矩阵 C=[cij]。 k 对列表 ((ui1, dj1),(ui2,dj2),...,(uik,djk)) 被认为是不相交的如果 i1 < 12 <..< ik 和 j1 < j2 <...< jk。 "compatibility of a list" 据说是构成它的对之和的相容性，即 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

我不太了解重复率，为什么我们在 t > min{n − i + 1, m − j + 1} 时将 −∞ 分配给 M(i, j, t)，而在 i > n 或 j > m 时分配 0

解是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，要么不增加长度并充分利用此（缺少）操作所带来的可能性。您可能会问 "but what about M(i+1,j+1,t)? that's also a valid possibility." 它是，但它包含在其他两种情况中：M(i+1,j,t) 将在需要时检查 M(i+1,j+1,t) 和 return 它。可以自己加到recurrence里面，不会错，只是多余。

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 则忽略此分支，尽管如果分支的 none 有效，您仍然需要 return 0/-infinity），但这并不重要。

如果您 return 0 而答案是否定的，那么您将运行陷入困境。当然，对于你的问题，由于 C 的构建方式，我们不能有否定的解决方案（因为 C 包含数字的平方，它们总是 >= 0 ）。因此，在第一种情况下，您也可以使用 0 而不是负无穷大。

练习：你能写出一个类似的递归式吗，但是M(n, m, k)给出了解决方案？先用文字定义，再用数学定义。

动态规划练习

Dynamic Programming Exercise

algorithm

dynamic

dynamic-programming