第9章｜动态规划
Unit 11 · LeetCode #1143 最长公共子序列
两个字符串的关系，
被压缩进一个前缀坐标。
本单元把一维的“以前驱结尾”扩展为二维前缀状态：dp[i][j] 同时概括 text1[:i] 与 text2[:j]。当前字符相等时接到左上角；不相等时必须明确丢弃哪一个末尾字符。
已恢复上次学习位置阶段、动画、答题、代码槽位和迁移进度均已恢复。
知识桥梁｜Unit 10 → Unit 11
Unit 10：一个结尾索引
dp[i] 表示必须以 nums[i] 结尾，扫描所有左侧合法前驱。
一个序列 → 两个前缀
Unit 11：两个前缀长度
dp[i][j] 同时描述两个字符串前缀，当前位置由字符关系决定依赖方向。
本单元贯穿问题当前字符相等吗？若不相等，上方与左方分别意味着丢弃哪个字符？
LeetCode #1143 原题题面转述、示例、约束与提交签名
题目要求
给定两个字符串 text1 和 text2，返回它们最长公共子序列的长度；若不存在公共子序列则返回 0。子序列允许删除字符，但剩余字符的相对顺序不能改变。
class Solution:
def longestCommonSubsequence(
self, text1: str, text2: str
) -> int:
pass
约束
1 ≤ len(text1), len(text2) ≤ 1000；- 两个字符串仅包含小写英文字母。
示例
输入：text1 = "abcde", text2 = "ace"
输出：3
解释：最长公共子序列为 "ace"。
输出：3
解释：最长公共子序列为 "ace"。
输入：text1 = "abc", text2 = "def"
输出：0
输出：0
主方法
二维前缀动态规划：时间复杂度 O(mn)，空间复杂度 O(mn)；可进一步压缩为 O(n)。
本环节已完成
页面停留在当前状态。请确认你能解释高亮依赖后再继续。