首页 > 试题广场 >

最长公共子序列

[编程题]最长公共子序列
  • 热度指数：13307 时间限制：C/C++ 3秒，其他语言6秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解

对于两个字符串，请设计一个高效算法，求他们的最长公共子序列的长度，这里的最长公共子序列定义为有两个序列U1,U2,U3...Un和V1,V2,V3...Vn,其中Ui&ltUi+1，Vi&ltVi+1。且A[Ui] == B[Vi]。

给定两个字符串A和B，同时给定两个串的长度n和m，请返回最长公共子序列的长度。保证两串长度均小于等于300。

测试样例：
"1A2C3D4B56",10,"B1D23CA45B6A",12
返回：6
算法知识视频讲解
开通博客
头像 重生之我要当分子
发表于 2024-12-31 23:55:00
解题思路 这是一个最长公共子序列(LCS)问题。关键点： 动态规划定义： 表示 的前 个字符和 的前 个字符的最长公共子序列长度 状态转移： 当 时： 否则： 边界条件： 代码 cpp java python class LCS { p 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

贪心 动态规划
来自：面试常考算法题(九)-...
难度：
62条回答 33383浏览

热门推荐

通过挑战的用户

查看代码

相关试题

最长公共子序列

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号