【蓝桥云课】最长公共子序列LCS_股票证券

【蓝桥云课】最长公共子序列LCS

创始人

2025-05-30 11:30:05

题目描述：输入两个字符串s和t，求它们的最长公共子序列(不连续)。

样例输入：

BDCABA
ABCBDAB

样例输出：

4
解释：s和t的最长公共子序列为BDAB、BCAB、BCBA,长度为4

方法：
定义dp[i][j]dp[i][j]dp[i][j]表示s1,s2,s3,....,sis_{1},s_{2},s_{3},....,s_{i}s1,s2,s3,....,si与t1,t2,t3,....,tjt_{1},t_{2},t_{3},....,t_{j}t1,t2,t3,....,tj的最长公共子序列；

那么
dp[i+1][j+1]={dp[i][j]+1,如果si+1=tj+1max(dp[i][j+1],dp[i+1][j]),如果si+1≠tj+1dp[i+1][j+1]=\begin{cases} dp[i][j]+1& \text{,如果$s_{i+1}=t_{j+1}$}\\ max(dp[i][j+1],dp[i+1][j])& \text{,如果$s_{i+1}≠t_{j+1}$} \end{cases}dp[i+1][j+1]={dp[i][j]+1max(dp[i][j+1],dp[i+1][j]),如果si+1=tj+1,如果si+1=tj+1

程序代码：

import java.util.Arrays;
import java.util.Scanner;public class LCS {public static void main(String[] args) {String s="",t="";Scanner sc = new Scanner(System.in);while(sc.hasNext()) {s=sc.next();t=sc.next();int[][] dp = new int[s.length()+1][t.length()+1];for(int i=0;ifor(int j=0;jif(s.charAt(i)==t.charAt(j)) {dp[i+1][j+1]=dp[i][j]+1;} else {dp[i+1][j+1]=Math.max(dp[i][j+1], dp[i+1][j]);}}}System.out.println(dp[s.length()][t.length()]);}}
}

上一篇：重大通报“九九联盟到底有透视挂是真的吗”(真的有挂)

下一篇：实测分享“天天云南麻将到底能开挂吗”(确实有挂)

【蓝桥云课】最长公共子序列LCS

相关内容

热门资讯