最长公共子序列
已关闭dadingPython / C++入场费 3 金币0 次提交
题目描述
给定两个字符串 s 和 t，求它们的最长公共子序列（LCS）的长度。
子序列的定义：在不改变字符相对顺序的前提下，从原字符串中删除若干字符后得到的新字符串。
两个字符串的公共子序列是同时为两个字符串子序列的字符串。
例如： s = "abcde" t = "ace" LCS = "ace"，长度为 3。
再例如： s = "abc" t = "def" LCS = ""（空串），长度为 0。
输入格式
两行，每行一个字符串，仅包含小写字母，长度 1~1000
输出格式
一个整数，表示最长公共子序列的长度
输入输出样例
样例 1
输入：
abcde ace
输出：
3
样例 2
输入：
abc def
输出：
0
样例 3
输入：
psnw ostj
输出：
1
说明/提示
二维 DP，dp[i][j] 表示 s[0..i) 和 t[0..j) 的 LCS 长度。转移方程：若 s[i-1]==t[j-1]，则 dp[i][j]=dp[i-1][j-1]+1；否则 dp[i][j]=max(dp[i-1][j], dp[i][j-1])。注意边界初始化。