解题思路：动态规划

• 定义状态：

  • 设 $dp[i][j]$ 表示 text1[0:i] 和 text2[0:j] 的 最长公共子序列 的长度。

• 状态转移方程：

  1. 如果 $text1[i-1] == text2[j-1]$，则当前字符匹配：$$dp[i][j] = dp[i-1][j-1] + 1$$

Leetcode 94.最长公共子序列-原题链接

题目描述

给定两个字符串 text1 和 text2，返回这两个字符串的 最长公共子序列 的长度。如果不存在公共子序列，则返回 0。

定义：

• 子序列：从原字符串中删除 某些字符（可不删除），但不改变剩余字符的 相对顺序，得到的新字符串。
• 公共子序列：两个字符串都包含的 子序列。

输入描述

输入包含两行：

• 第一行是字符串 text1（$1 \leq |text1| \leq 1000$）。
• 第二行是字符串 text2（$1 \leq |text2| \leq 1000$）。

text1 和 text2 仅由小写英文字符组成。

输出描述

输出一行，表示 最长公共子序列 的长度。

样例输入 1

abcde
ace

样例输出 1

3

说明：最长公共子序列是 "ace"，长度为 3。

样例输入 2

abc
abc

样例输出 2

3

说明：最长公共子序列是 "abc"，长度为 3。

样例输入 3

abc
def

样例输出 3

0

说明：两个字符串没有公共子序列，返回 0。