最长公共子序列 题目描述：给定两个字符串text1和text2，返回这两个字符串的最长公共子序列的长度。如果不存在公共子序列，返回0。子序列是指在不改变剩余字符相对顺序的情况下，删除某些字符（也可以不删除）后形成的新字符串。 解题过程： 问题分析 我们需要找到两个字符串中都出现的最长子序列。注意子序列不要求连续，但必须保持原有顺序。例如text1="abcde", text2="ace"，最长公共子序列是"ace"，长度为3。 定义状态 定义dp[ i][ j ]表示text1的前i个字符和text2的前j个字符的最长公共子序列长度。i和j从1开始计数。 状态转移方程 如果text1[ i-1] == text2[ j-1 ]（字符匹配）： dp[ i][ j] = dp[ i-1][ j-1 ] + 1 因为当前匹配的字符可以加入公共子序列 如果text1[ i-1] != text2[ j-1 ]（字符不匹配）： dp[ i][ j] = max(dp[ i-1][ j], dp[ i][ j-1 ]) 取text1少一个字符或text2少一个字符时的最大值 初始化 dp[ 0][ j ] = 0（text1为空字符串） dp[ i][ 0 ] = 0（text2为空字符串） 计算顺序 按i从1到m（text1长度），j从1到n（text2长度）的顺序计算 示例演示 以text1="abcde", text2="ace"为例： 初始化5×4的dp表，第一行和第一列为0 逐步填充： (1,1): 'a'='a' → dp[ 1][ 1 ]=1 (1,2): 'a'≠'c' → max(0,1)=1 (1,3): 'a'≠'e' → max(0,1)=1 (2,1): 'b'≠'a' → max(1,0)=1 (2,2): 'b'≠'c' → max(1,1)=1 (2,3): 'b'≠'e' → max(1,1)=1 (3,1): 'c'≠'a' → max(1,0)=1 (3,2): 'c'='c' → 1+1=2 继续计算直到dp[ 5][ 3 ]=3 结果提取 最终结果为dp[ m][ n ]，即整个字符串的最长公共子序列长度。