最长公共子序列

题目要求：对字符串S1（长度为n）和S2（长度为m）求公共子串S3，并且S3的长度最大，求该长度

动态规划分析：

保存结果：dp[i][j]表示以S1[i]结尾和S2[j]结尾的最长公共子序列的长度

递推起点： dp[i][0] = 0; dp[0][j] = 0;（同时也是边界值处理）

递推公式：

①如果S1[i] == S2[j] => dp[i][j] = dp[i - 1][j - 1] + 1

②如果S1[i] != S2[j] => dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

最终解为：dp[n - 1][m - 1]（下标从1开始）

def maxCommonSubSeq():
    while True:
        try:
            s1 = input()
            s2 = input()
            # 给s1和s2前面拼接一个空串，使得字符串实际内容下标从1开始
            s1 = '\0' + s1
            s2 = '\0' + s2
            n = len(s1)
            m = len(s2)
            dp = [[0 for j in range(m)] for i in range(n)]
            for i in range(n):
                dp[i][0] = 0 # 边界值
                for j in range(m):
                    dp[0][j] = 0 # 边界值
                    if s1[i] == s2[j]:
                        dp[i][j] = dp[i - 1][j - 1] + 1
                    else:
                        dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
            print(dp[n - 1][m - 1]) # 最终解
        except (EOFError, KeyboardInterrupt):
            break


if __name__ == '__main__':
    maxCommonSubSeq()