day57 动态规划part14 代码随想录算法训练营 1143. 最长公共子序列

题目：1143. 最长公共子序列

我的感悟：

• 你永远不知道自己有多厉害！加油！

理解难点：

• 递推公式如何想，
• 通过图，来记忆。

听课笔记：

我的代码：

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        # 假设text1为内层,text2为外层
        n = len(text1)
        w = len(text2)
        dp = [[0]*(n+1) for _ in range(w+1)]    # 初始化注意
        for i in range(1,w+1):  # 外层text2
            for j in range(1,n+1):    # 内层text1
                if text2[i-1] == text1[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]

通过截图：

易错点：

• 初始化dp=[[0]...]这个0要加【】
• if 判断，要加text1[i-1] == text2[j-1] 注意这个-1

老师代码：

扩展写法：

资料：

1143.最长公共子序列 

体会一下本题和 718. 最长重复子数组 的区别  

视频讲解：https://www.bilibili.com/video/BV1ye4y1L7CQ

https://programmercarl.com/1143.%E6%9C%80%E9%95%BF%E5%85%AC%E5%85%B1%E5%AD%90%E5%BA%8F%E5%88%97.html