python3动态规划

实际上是最长连续公共子串

class Solution:
    def LCS(self , str1 , str2 ):
        n, m = len(str1), len(str2)
        dp = [[0] * (m+1) for _ in range(n+1)]
        p = (0,0)
        for i in range(1,n+1):
            for j in range(1,m+1):
                tmp = int(str1[i-1] == str2[j-1])
                dp[i][j] = dp[i-1][j-1] + tmp if tmp else 0
                p = (i,j) if dp[i][j] > dp[p[0]][p[1]] else p
        return str1[p[0]-dp[p[0]][p[1]]:p[0]]