ACM试题 - 最长公共子序列 - 动态规划方法

向右看齐 2021-12-08 22:47 134阅读 0赞

## ACM试题题源-(最长公共子序列)：[http://acm.nyist.net/JudgeOnline/problem.php?pid=36][http_acm.nyist.net_JudgeOnline_problem.php_pid_36] ##

提交代码：

import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner cin = new Scanner(System.in); int n = cin.nextInt(); int[] len = new int[n]; for (int k = 0; k < n; k++) { String s1 = cin.next(); String s2 = cin.next(); int[][] m = new int[s1.length()+1][s2.length()+1]; for (int i = 0; i < s1.length(); i++) { for (int j = 0; j < s2.length(); j++) { m[i][j] = 0; } } for (int i = 0; i < s1.length(); i++) { for (int j = 0; j < s2.length(); j++) { if (s1.charAt(i) == s2.charAt(j)) { m[i + 1][j + 1] = m[i][j] + 1; } else { m[i + 1][j + 1] = Math.max(m[i][j + 1], m[i + 1][j]); } } } len[k] = m[s1.length()][s2.length()]; } for (int i = 0; i < n; i++) { System.out.println(len[i]); } } }

参考资料：[http://blog.chinaunix.net/uid-26548237-id-3374211.html][http_blog.chinaunix.net_uid-26548237-id-3374211.html]

转载于:https://www.cnblogs.com/louislee92/p/3921804.html

[http_acm.nyist.net_JudgeOnline_problem.php_pid_36]: http://acm.nyist.net/JudgeOnline/problem.php?pid=36
[http_blog.chinaunix.net_uid-26548237-id-3374211.html]: http://blog.chinaunix.net/uid-26548237-id-3374211.html

发表评论取消回复

表情：

评论列表（有 0 条评论，134人围观）

还没有评论，来说两句吧...

相关阅读

相关 [动态规划][公共子串]最长公共子串、最长公共子序列

1、最长公共子串 LintCode：[https://www.lintcode.com/problem/longest-common-substring/descri...

约定不等于承诺〃/ 2024年04月18日 17:10/ 0 赞/ 72 阅读

相关动态规划：最长公共子序列

动态规划：最长公共子序列前言一、动态规划 -------------------- 前言给定两个字符串 text1 和 text2，返回这两个

妖狐艹你老母/ 2024年03月16日 18:40/ 0 赞/ 108 阅读

相关最长公共子序列（动态规划）

【题⺫】给定两个字符串 str1 和 str2，返回两个字符串的最长公共子序列。【举例】 str1 =“1 A2 C 3 D 4 B5 6 ”， str2

本是古典何须时尚/ 2022年08月18日 02:19/ 0 赞/ 230 阅读

相关 ACM最长公共子序列问题（动态规划）C++实现

// 最长公共子序列问题.cpp : Defines the entry point for the console application. //动态规划问题对于X=

喜欢ヅ旅行/ 2022年06月18日 11:11/ 0 赞/ 89 阅读

相关最长公共子序列（动态规划）

【例9.9】最长公共子序列时间限制: 1000 ms 内存限制: 65536 KB 【题目描述】一个给定序列的子序列是在该序列中删去若干元素后得到

╰半橙微兮°/ 2022年06月08日 10:06/ 0 赞/ 264 阅读

相关 ACM最长公共子序列问题（动态规划）C++实现

// 最长公共子序列问题.cpp : Defines the entry point for the console application. //动态规划问题对于X=

我不是女神ヾ/ 2022年05月15日 13:15/ 0 赞/ 92 阅读

相关 ACM最长公共子序列问题（动态规划）C++实现

// 最长公共子序列问题.cpp : Defines the entry point for the console application. //动态规划问题对于X=

曾经终败给现在/ 2022年05月15日 13:15/ 0 赞/ 118 阅读

相关动态规划-最长公共子序列

一，问题描述给定两个字符串，求解这两个字符串的最长公共子序列（Longest Common Sequence）。比如字符串1：BDCABA；字符串2：ABCBDAB 则这

痛定思痛。/ 2022年05月11日 11:50/ 0 赞/ 301 阅读

相关 ACM试题 - 最长公共子序列 - 动态规划方法

ACM试题题源-(最长公共子序列)：[http://acm.nyist.net/JudgeOnline/problem.php?pid=36][http_acm.nyist.

向右看齐/ 2021年12月08日 22:47/ 0 赞/ 135 阅读

相关【动态规划】最长公共子序列与最长公共子串

[来源][Link 1] 1. 问题描述子串应该比较好理解，至于什么是子序列，这里给出一个例子：有两个母串 cnblogs belong 比如序列

「爱情、让人受尽委屈。」/ 2021年06月24日 16:12/ 0 赞/ 543 阅读