Java实现算法之最大公共子序列_java求最大公共子序列

作者：2023面试高手 | 2024-03-05 20:31:27

踩

java求最大公共子序列

题目：

一个字符串A的子序列被定义成从A中顺次选出若干个字符构成的序列。如A=“cdaad" ,顺次选1，3，5个字符就构成子序列" cad" ,现给定两个字符串，求它们的最长公共子序列。

输入格式：第一行两个字符串用空格分开。

输出格式：最长序列的长度。

两个串的长度均小于2000

abccd aecd

思路：

这个题要用到动态规划，因此需要写出状态转移方程：

C[i,j]存放的就是最大公共子序列的长度，i和j分别是两字符串的下标。

本文内容由网友自发贡献，转载请注明出处：https://www.wpsshop.cn/w/2023面试高手/article/detail/193650