技术标签： JAVA 算法 DP算法 JAVA算法学习 最长公共子序列 算法设计 算法分析与设计
最长公共子序列问题： 给定两个字符串A、B，求A与B的最长公共子序列（子序列不要求是连续的）
举例：
字符串A： abcicba
字符串B：abdkscab
其中:ab、abc、abca都是公共子序列，但是abca是最长公共子序列
从文件读取输入：
1A2C3D4B56
B1D23CA45B6A
输出：
123456
或者 12C4B6都正确
package com.bean.algorithmexec;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;
public class LCS {
/*
* 最长公共子序列问题 给定两个字符串A、B，求A与B的最长公共子序列（子序列不要求是连续的）
* 举例：
* 字符串A： abcicba
* 字符串B：abdkscab
* 其中:ab、abc、abca都是公共子序列，但是abca是最长公共子序列
*
* 从文件读取输入：
* 1A2C3D4B56
* B1D23CA45B6A
*
* 输出：
* 123456
*
* 或者 12C4B6都正确
*
* （这里的算法其实存在一个缺陷）
*/
public static void main(String[] args) throws FileNotFoundException {
// TODO Auto-generated method stub
System.setIn(new FileInputStream("G:\\lcs.txt"));
Scanner sc = new Scanner(System.in);
String aStr = sc.nextLine(); //读取A字符串
String bStr = sc.nextLine(); //读取B字符串
int aLen = aStr.length();
int bLen = bStr.length();
//构造DP矩阵
int[][] dp = new int[aLen + 1][bLen + 1];
for (int i = 1; i < aLen + 1; i++)
for (int j = 1; j < bLen + 1; j++)
if (dp[i - 1][j] == dp[i][j - 1] && aStr.charAt(i - 1) == bStr.charAt(j - 1)
&& dp[i - 1][j] == dp[i - 1][j - 1])
dp[i][j] = dp[i - 1][j] + 1;
else
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
int max = dp[aLen][bLen];
StringBuilder sb = new StringBuilder();
while (max > 0) {
if (dp[aLen - 1][bLen] == dp[aLen][bLen - 1] && dp[aLen - 1][bLen] + 1 == dp[aLen][bLen]) {
sb.append(aStr.charAt(aLen - 1));
max--;
aLen--;
bLen--;
} else {
if (dp[aLen][bLen - 1] == dp[aLen][bLen])
bLen--;
else
aLen--;
}
}
System.out.println(sb.reverse().toString());
}
}
这个问题是一个经典的动态规划问题，先来介绍求解动态规划表的过程。
第1步：
如果str1的长度为M，str2的长度为N，则生成大小为M*N的矩阵dp，行数为M行，列数为N列。
d p [ i ] [ j ] dp[i][j] dp[i][j]的含义是 s t r 1 [ 0... i ] str1[0...i] str1[0...i]与 s t r 2 [ 0... j ] str2[0...j] str2[0...j]的最长公共子序列的长度。从左向右，从上向下计算矩阵dp。
其中：记str1中从第0个字符到第i个字符为 s t r 1 [ 0... i ] str1[0...i] str1[0...i]；记str2中从第0个字符到第j个字符为 s t r 2 [ 0... j ] str2[0...j] str2[0...j]。
矩阵dp第一列即 d p [ 0... M − 1 ] [ 0 ] dp[0...M-1][0] dp[0...M−1][0]， d p [ i ] [ 0 ] dp[i][0] dp[i][0]的含义是 s t r 1 [ 0... i ] str1[0...i] str1[0...i]与 s t r 2 [ 0 ] str2[0] str2[0]的最长公共子序列长度。
s t r 2 [ 0 ] str2[0] str2[0]只有一个字符，所以 d p [ i ] [ 0 ] dp[i][0] dp[i][0]最大为1。如果 s t r 1 [ i ] = = s t r 2 [ 0 ] str1[i]==str2[0] str1[i]==str2[0]，令 d p [ i ] [ 0 ] = 1 dp[i][0]=1 dp[i][0]=1，一旦 d p [ i ] [ 0 ] dp[i][0] dp[i][0]被置为1，之后的 d p [ i + 1... M − 1 ] [ 0 ] dp[i+1...M-1][0] dp[i+1...M−1][0]也都为1。
例如： s t r 1 [ 0... M
文章浏览阅读10w+次，点赞143次，收藏775次。今天为大家介绍如何才能启用Windows10下的Linux子系统，废话不多说，直接看步骤：启用开发者模式打开设置 点击更新和安全 点击开发者选项 启用开发人员模式 更改系统功能使用win+X快捷键调出系统管理菜单后点击应用和功能，然后拉到底下，选择程序和功能 选中应用或关闭Windows功能 勾选适用于Linux的Windows子系统，然后确认并重启..._win10自带linux子系统怎么用
文章浏览阅读1.9w次，点赞46次，收藏113次。前言满纸荒唐言，一把辛酸泪。都云作者痴，谁解其中味？只有我的电脑知道为了安装Latex排版的工具花了多少功夫，查了多少资料。斗争之旅我的电脑上很早就有老师给的CTEX安装包，并且安装的时候还是百度了一下安装步骤，生怕到时候会有问题。结果等到我要开始写SCI论文的时候才发现，咦？ 这是啥错误undefined control sequence\begin{document}，改了路径啥的好多操作都不行，于是卸载，结果发现卸载都卸载不掉，文件都删除不了，后面我慢慢删也是删完了，后面还发现居然还修改_texlive
文章浏览阅读169次。通过提取平面近点的方法，将道路点云和其他树木等点云分割开，具体的效果如下：（左）其他点云 （右）道路点云。
文章浏览阅读188次。1. 前言我们先思考下面几个业务场景的解决方案:支付系统每天凌晨1点跑批，进行一天清算，每月1号进行上个月清算电商整点抢购，商品价格8点整开始优惠12306购票系统，超过30分钟没有成功支付订单的，进行回收处理商品成功发货后，需要向客户发送短信提醒“类似的业务场景非常多，我们怎么解决？”很多业务场景需要我们某一特定的时刻去做某件任务，定时任务解决的就是这种业务场景。一般来说，系统可以使用消息传递代..._定时任务中间件选择
文章浏览阅读6.2k次，点赞43次，收藏29次。我们基于 Hello 驱动程序先写出最简单的 LED 驱动程序_linux驱动怎么写
文章浏览阅读270次。RabbitMQ学习文档_mq学习文档
文章浏览阅读2k次。h.265解码库，支持GPU和CPU1.初始化PlayerSDK_Init(CallBack callBackFunc,int nType);callBackFunc 回调函数nType 视频解码方式 CPU解码或者GPU解码2.播放接口PlayerSDK_Play(char* URL, long hWnd, int nType);URL 播放地址hWnd 播放句柄nType 播放类型接口返回播放句柄号3.停止播放接口Play_h265能通过gpu解码
文章浏览阅读2.1k次。有一个坑一直没过去，就是如果整体环境没完全装好，但是使用我自己提前创建的python虚拟环境来启动SD启动脚本stable-diffusion-webui/webui-user.bat，期间会因为某些原因（比如没梯子东西下载不下来）启动失败，但是第二次启动时就会报没有pip模块的错误，我就只能重新创建python虚拟环境，再装一遍包，这个过程很漫长很浪费时间，所以一定跟着我的脚步，一步不要落下的走，心急吃不了热豆腐。如果没有梯子，这里很慢或者根本过不去，所以参考。三、修改url地址（梯子强可不改）_sd webui torch版本
文章浏览阅读491次。CTFSHOW做题记录**CTFSHOW做题记录1**（菜菜的我要写日记啦，欢迎大佬指导）**密码学签到1给出“}wohs.ftc{galf”并且提示倒叙。**解题思路：没看提示的时候乍一看以为是栅栏密码，还想着用在线解密去做，但是定睛一看不对劲，再看题目原来就是倒叙。只需要反着来就好啦。**答案：flag{ctf.show}**今天也是元气满满的一天，好好学习。..._ctfshow 龙猫
文章浏览阅读1.9k次。不同的方法适用于不同的情况，例如如果目标网站使用的是JavaScript动态加载数据，那么使用Scrapy-Splash可能会更加适合。如果目标网站的数据比较简单，那么使用浏览器开发者工具可能会更加方便。如果需要模拟用户的操作，那么使用Selenium可能是更好的选择。总之，需要根据具体情况选择合适的方法，才能高效地获取动态网页的数据。综上所述，选择合适的方法取决于具体的需求。如果需要模拟用户的操作，可以使用Selenium。动态网页是指在用户交互过程中，网页内容不断更新和变化的网页。_动态加载的网页怎么获取链接
文章浏览阅读1k次，点赞3次，收藏6次。下载最新版本：https://sunlogin.oray.com/download/缺少部分依赖，手动下载：# 你知道最新的版本号了sudo wget http://download.oray.com/sunlogin/linux/SunloginClient-10.0.2.24779_amd64.debsudo wget http://mirrors.aliyun.com/ubuntu/pool/main/i/icu/libicu60_60.2-3ubuntu3_amd64.debsudo w_ubuntu20.04 安装向日库
文章浏览阅读635次，点赞14次，收藏7次。打开IE浏览器，点击右上方工具按钮，依次选择“Internet选项” -> “连接” -> “局域网设置” -> “代理服务器”，勾选“为LAN使用代理服务器”，输入本地IP地址127.0.0.1及端口号8888，点击确定保存。若页面提示“此网站的安全证书存在问题”，点击“继续浏览此网站(不推荐) ”即可。4.选择“Requests Filtering”，在“包含模式”中填入“.+(baidu.com).+”用以过滤非。选中“工作台”，右键选择“添加” -> “非测试元件” -> “HTTP代理服务器”