最長共通サブシーケンスLCS理解と実装[python]

問題:2つの文字列S 1とS 2を与えて、この2つの文字列の最も長い共通のサブシーケンスの長さを求めます
例:
S 1=ABCD,S 2=AEBD,最長共通サブシーケンス長3
考え方:
    1.トップダウンの方法
|-遡及法:時間複雑度O(2^n*n)
|-2つの文字列の最後の文字を比較し、等しい場合と等しくない場合に分けます.
|-等しい:res=1+back(m-1,n-1)
|-等しくない:res=max(back(m,n-1),back(m-1,n))
|-ここでm,nはそれぞれ2つの文字列の最後の要素のインデックスであり、backは再帰的に呼び出された最長の共通サブシーケンスを探す関数である.
|-構造化子関数:時間複雑度O(m*n)
    2.下から上へのアプローチ
|-2 Dダイナミックプランニング:
|-状態LCS(m,n):S 1[0...m]およびS 2[0...n]の最長共通サブシーケンスの長さを表す
|-m,nはLCSで新しく追加された2文字であり,現在この2文字が追加された後の状態遷移を考慮するだけでよい.
|-状態遷移方程式は2つのケースに分けられる.
                |-1. S1[m] == S2[n]: LCS(m, n)=1+LCS(m-1,n-1)
                |-2. S1[m] != S2[N]: LCS(m, n)=max(Lcs(m-1, n), LCS(m, n-1))
|-時間複雑度O(m*n)
github:クリックしてリンクを開く
pythonソースコード:

class Solution(object):
    # 1    
    def back(self, S1, S2):
        m = len(S1)-1
        n = len(S2)-1
        #     
        if m < 0 or n < 0:
            return 0
        #     
        if S1[m] == S2[n]:
            return 1+self.back(S1[:m], S2[:n])
        else:
            #    
            return max(self.back(S1[:m], S2), self.back(S1, S2[:n]))

    # 2       
    def childS(self, S1, S2):
        m = len(S1) - 1
        n = len(S2) - 1
        rows = [-1 for i in range(n + 1)]
        memo = [rows.copy() for j in range(m + 1)]
        return self.struct(S1, S2, memo)
    def struct(self, S1, S2, memo):
        m = len(S1) - 1
        n = len(S2) - 1
        #     
        if m < 0 or n < 0:
            return 0

        if S1[m] == S2[n]:
            if memo[m-1][n-1] == -1:
                memo[m - 1][n - 1] = self.struct(S1[:m], S2[:n], memo)+1
            return memo[m-1][n-1]
        else:
            if memo[m-1][n] == -1:
                memo[m - 1][n] = self.struct(S1[:m], S2, memo)
            if memo[m][n-1] == -1:
                memo[m][n - 1] = self.struct(S1, S2[:n], memo)
            return max(memo[m][n - 1], memo[m-1][n])

    # 3     
    def dp(self, S1, S2):
        m = len(S1)
        n = len(S2)
        if m < 0 or n < 0:
            return 0
        memo = [[0]*(n+1) for j in range(m+1)]
        #       0   0    0
        for i in range(1, m+1):
            for j in range(1, n+1):
                if S1[i-1] == S2[j-1]:  # S1   i    S2   j   
                    memo[i][j] = 1 + memo[i-1][j-1]
                else:
                    memo[i][j] = max(memo[i-1][j], memo[i][j-1])
        return memo[m][n]

S1 = 'AFDSAFDSA'
S2 = 'FDSAFD'
print(Solution().dp(S1, S2))class Solutio