编程题：最长公共子序列

也就是LCS问题，常规的动态规划题目，状态转移矩阵见下图：

代码呼之欲出：

class Solution:
    def lsc(self, a, b):
        len_a, len_b = len(a), len(b)
        # dp[i][j]表示a的前i个数和b的前j个数构成的最长公共子串长度
        dp = [[0] * (len_b + 1) for _ in range(len_a + 1)]
        for i in range(1, len_a + 1):
            for j in range(1, len_b + 1):
                if a[i - 1] == b[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1] + 1
                else:
                    dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])
        return dp[-1][-1]


if __name__ == '__main__':
    print(Solution().lsc('13456778', '357486782'))
           

这里答案是5

上一步只是求出了最长公共子序列的长度，这里要求出最长公共子序列。可以在dp的时候用一个空间来存每一步的子串，也可以用回溯的思想来求最长公共子序列。如果是从左上角来的，就加入，如果不是就看左边或上边那个大的，如果相同就任选一个方向走：

class Solution:
    def lsc(self, a, b):
        len_a, len_b = len(a), len(b)
        # dp[i][j]表示a的前i个数和b的前j个数构成的最长公共子串长度
        dp = [[0] * (len_b + 1) for _ in range(len_a + 1)]
        for i in range(1, len_a + 1):
            for j in range(1, len_b + 1):
                if a[i - 1] == b[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1] + 1
                else:
                    dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])
        i, j, res = len_a, len_b, ''
        while i > 0 and j > 0:
            if a[i - 1] == b[j - 1]:
                res = a[i - 1] + res
                i -= 1
                j -= 1
            elif dp[i - 1][j] > dp[i][j - 1]:  # 上走
                i -= 1
            else:  # 左走
                j -= 1
        return res


if __name__ == '__main__':
    print(Solution().lsc('13456778', '357486782'))
           

结果是35778，如果把

elif dp[i - 1][j] > dp[i][j - 1]:  # 上走
                i -= 1
            else:  # 左走
                j -= 1
           

变成

elif dp[i - 1][j] >= dp[i][j - 1]:  # 上走
                i -= 1
            else:  # 左走
                j -= 1
           

就又是一种结果：34678。