动态编程--3 sequences.and求最大值

Question

Question I need Help with: CHECK HERE

我需要一些帮助来解决这个问题。

到目前为止，我想出的解决方案是：

将B视为输入并向后返回，因此取B的最后一个值并从后面查找A以查找与B匹配的值。然后取B的第一个值并从前面查找A并找到第一个匹配的值。保存这两个值。

然后在两个上限和下限之间进行比较，以找到比第一步中找到的值更大的值。这样它才能满足要求。所以在问题B= (x，y)中给出的例子中，X必须在Y之前，所以即使有最大的X在最后一个Y之后，我们也不能选择它。

我相信它会在O(MxN)时间内运行，但我非常不确定，这就是为什么我问你们。

感谢您的时间，希望你们能帮助我。

Answer 1

你的解决方案听起来一点也不像动态编程。

这个问题基本上是要求找到一个最大和longest common subsequence，其中公共子序列在A和B之间，和来自P。

应该可以针对您的问题调整LCS解决方案。由于您必须从P中选取总和，因此在构建LCS矩阵后，请考虑使用经典回溯算法来获得实际的LCS：

backtrack(LCS, A, B, i, j):
    if i == 0 or j == 0
        return ""

    if A[i] == B[j]:
        return backtrack(LCS, A, B, i-1, j-1) + A[i]
    else if LCS[i-1, j] > LCS[i, j-1]:
        return backtrack(LCS, A, B, i-1, j)
    return backtrack(LCS, A, B, i, j-1)

现在你需要找到最大和：

backtrack(LCS, A, B, i, j, s=0):
    if i == 0 or j == 0
        return s

    if A[i] == B[j]:
        return backtrack(LCS, A, B, i-1, j-1, s + P[i])
    else if LCS[i-1, j] > LCS[i, j-1]:
        return backtrack(LCS, A, B, i-1, j, s)
    else if LCS[i-1, j] < LCS[i, j-1]:
        return backtrack(LCS, A, B, i, j-1, s)
    else:
        return max(backtrack(LCS, A, B, i-1, j, s),
                   backtrack(LCS, A, B, i, j-1, s))

您可能必须应用memoization才能有效地实现。还可以与LCS矩阵一起计算和矩阵(或者甚至代替LCS矩阵)。