python - 我的最长公共(public)子序列 python 中的逻辑错误

Question

我已经在 python 中使用动态编程实现了最长公共(public)子序列的解决方案。对于那些不了解 LCS 的人，请点击此处。

https://www.tutorialspoint.com/design_and_analysis_of_algorithms/design_and_analysis_of_algorithms_longest_common_subsequence.htm

我的代码没有返回最佳答案。我的逻辑有什么问题？

import enum

class LCS:

    class Dir(enum.Enum):
        up = 1
        diagonal = 2
        left = 3
        none = 0

    def LCS(self, x, y):
        self.DP = {}
        m = len(x) - 1
        n = len(y) - 1
        self.recursion(x, y, m, n)
        print(self.DP)
        self.printLCS(x, m, n)

    def recursion(self, x, y, i, j):
        if i == 0 or j == 0:
            return [0, self.Dir.none]
        else:
            if (i, j) not in self.DP:
                if x[i] == y[j]:
                    cost = self.recursion(x, y, i - 1, j - 1)[0] + 1
                    dir = self.Dir.diagonal
                else:
                    first = self.recursion(x, y, i - 1, j)
                    second = self.recursion(x, y, i, j - 1)
                    if first[0] >= second[0]:
                        cost = first[0]
                        dir = self.Dir.up
                    else:
                        cost = second[0]
                        dir = self.Dir.left

                self.DP[(i, j)] = [cost, dir]

        return self.DP[(i, j)]

    def printLCS(self, string, i, j):
        if i == 0 or j == 0:
            return
        elif self.DP[(i, j)][1] == self.Dir.diagonal:
            self.printLCS(string, i - 1, j - 1)
            print(string[i], end="")
        elif self.DP[(i, j)][1] == self.Dir.up:
            self.printLCS(string, i - 1, j)
        else:
            self.printLCS(string, i, j - 1)


x = "BDCABA"
y = "ABCBDAB"
sol = LCS()
sol.LCS(x, y)

预期=“BCBA”，实际=“DAB”

Answer 1

问题是你的基础状态。

python中的字符串是0基的，导致字符串s的第一个字符不是s[1]而是s[0]，你必须结束当您到达第一个元素之前而不是第一个元素时，您的递归。

只需在函数 printLCS 和递归中将 if i == 0 or j == 0: 替换为 if i == -1 or j == -1:您将得到输出 BDAB，这是正确答案之一。