问题：
题目来源：力扣（LeetCode）
leetcode1143.最长公共子序列
难度：中等
分析： 经典的动态规划题。 一个小技巧，在DP表的第一行和第一列添加辅助行和辅助列，这样就免去了初始化时的麻烦。本题可以从辅助行和辅助列得到需要的base case，所以可以使用这个技巧。
解决方法： 1：二维DP
递推公式为 if text1[i - 1] == text2[j - 1]：dp[i][j] = dp[i - 1][j - 1] + 1， if text1[i - 1] ！= text2[j - 1]：dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])， 因为添加了辅助行和辅助列，所以text的索引记得减一。
class Solution: def longestCommonSubsequence(self, text1: str, text2: str) -> int: m, n = len(text1), len(text2) dp = [[0] * (n + 1) for _ in range(m + 1)] for i in range(1, m + 1): for j in range(1, n + 1): if text1[i - 1] == text2[j - 1]: dp[i][j] = dp[i - 1][j - 1] + 1 else: dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) return dp[-1][-1]2：空间优化 O(2n) 需要两行来进行迭代，因为dp[i][j]需要从dp[i - 1][j - 1]中推导来，不能直接用一行来迭代，只能优化到O(2n)了。
class Solution: def longestCommonSubsequence(self, text1: str, text2: str) -> int: m, n = len(text1), len(text2) pre = [0] * (n + 1) cur = [0] * (n + 1) for i in range(1, m + 1): cur[0] = 0 for j in range(1, n + 1): if text1[i - 1] == text2[j - 1]: cur[j] = pre[j - 1] + 1 else: cur[j] = max(pre[j], cur[j - 1]) pre = cur[:] return cur[-1]建表示例： 辅助行、辅助列示例。 图片来源：https://leetcode-cn.com/problems/longest-common-subsequence/solution/dong-tai-gui-hua-zhi-zui-chang-gong-gong-zi-xu-lie/
