最長共通部分問題のPythonで記述

最長共通部分問題について、pythonで解いてみた。 もしかしたら、間違っているかも

class LCS(object):
    def __init__(self, s, t):
        self.s = s
        self.t = t
        self.n = len(s)
        self.m = len(t)
        self.dp = [[-1 for mm in range(self.m + 1)] for nn in range(self.n + 1)]

    def solve(self, i, j):
        if self.dp[i][j] >= 0:
            return self.dp[i][j]
        if i == 0 or j == 0:
            return 0
        if self.s[i - 1] == self.t[j - 1]:
            self.dp[i][j] = max(self.solve(i - 1, j - 1) + 1, self.solve(i, j - 1), self.solve(i - 1, j))
        else:
            self.dp[i][j] = max(self.solve(i, j-1), self.solve(i-1, j))
        res = self.dp[i][j]
        return res

    def get_lcs(self):
        return self.solve(self.n, self.m)

In [53]: lcs = LCS('abcd', 'becd')

In [54]: lcs.get_lcs()
Out[54]: 3

d.hatena.ne.jp