技术标签： 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
文章浏览阅读193次。杭州站总结 终于知道为什么老王说每次比赛完都有退队的了，我终于深有体会，但是老王请放心，我们还没有那么脆弱 ———题记 这次杭州比赛打铁而归，可以说是对不起父老乡亲了，更对不起老王，打铁已经在预料之中，但没想到会输的那么惨，回到开封，回到宿舍，突然有种做梦的感觉，分不清到底杭州是梦，还是现在是梦，总感觉很不真实，这_距上次坐火车应该是十年前
文章浏览阅读67次。一、负载均衡集群介绍负载均衡集群：简单地说就是让多台服务器均衡地去承载压力。实现负载均衡的开源软件有：LVS，keepalived，haproxy,nginx等其中相对于（网络OSI七层模型），LVS属于四层，Nginx属于七层，haproxy既可以认为四层，也可以认为是七层。keepalived的负载均衡功能其实就是lvslvs这种4层的负载均衡是可以分发出80外的其他端口通..._18.6 负载均衡集群介绍 18.7 lvs介绍 18.8 lvs调度算法 18.9/18.10 lvs nat模式搭
文章浏览阅读2.2k次。点击上方“小白学视觉”，选择加"星标"或“置顶”重磅干货，第一时间送达编辑：忆臻本文仅作为学术分享，如果侵权，会删文处理机器学习算法与自然语言处理报道有哪些好看的CNN模型画法？作者：bi..._cnn模型图
文章浏览阅读2.2k次，点赞6次，收藏8次。说起安卓开发，很多小伙伴在刚开始入门的时候会有些云里雾里，觉得很混乱，这很正常，大多数是因为不太清楚安卓开发的基本流程，以及各个文件之间是怎样去相互作用的。我会在这篇文章里面向你介绍一下Android studio工作的基本流程，很基础很基础的那种。_layout xml 怎么加载到view r 怎么取到
文章浏览阅读657次，点赞5次，收藏12次。采用现有无人车导航系统进行农作物育种表型信息的监测与采集时，存在因育种小区数量较多导致的导航目标点人工测量工作量大的问题，且育种田块不同于大田作物以A-B 线为基线的路径规划方法，无人车需要根据育种材料编号自动行进到某一指定位置进行作物表型信息采集。因此，为提高导航效率和降低人工劳动强度，本文基于无人机遥感对无人车的导航系统进行了研究。通过无人机获取玉米育种田的遥感影像并进行拼接和位置矫正，生成正射影像和数字地表模型（Digital Surface Model，DSM）。
文章浏览阅读7.8k次。开发环境vs2010css:bootstrapjs:jquery bootstrap paginator原先只是想做个mvc的分页，但是一般的数据展现都需要检索条件，而且是多个条件，所以就变成了MVC多条件+分页查询因为美工不是很好，所以用的是bootstrap前端框架，自己懒得写前端的分页控件，用的是bootstrap paginator分页控件。方式： _.net core mvc+bootstrap 页面分页查询
文章浏览阅读1.3k次。从 eclipse 切换到 idea 的时候遇到了头疼的问题：找不到主类直接说怎么解决的把：在原项目路径下先新建一个项目覆盖上去，如果没有 Intellij 原生目录(比如：.idea、out、src这些)，程序怎么都跑不起来；快捷键 ctrl+alt+shift+s 把 project structure 打开，配置好 project 的 sdk 和 compiler output；最..._idea 怎么找项目的主程序
文章浏览阅读954次。遗传算法求解天线线性阵列分布优化问题完整的代码，方可运行；可提供运行操作视频！适合小白！_matlab遗传算法优化阵列天线
文章浏览阅读102次。1 深度极限学习机人工神经网络的最大缺点是训练时间太长从而限制其实时应用范围,近年来,极限学习机(Extreme Learning Machine, ELM)的提出使得前馈神经网络的训练时间大大缩短,然而当原始数据混杂入大量噪声变量时,或者当输入数据维度非常高时,极限学习机算法的综合性能会受到很大的影响。深度学习算法的核心是特征映射,它能够摒除原始数据中的噪声,并且当向低维度空间进行映射时,能够很好的起到对数据降维的作用,因此我们思考利用深度学习的优势特性来弥补极限学习机的弱势特性从而改善极限学习机的性能。_群搜索 gso 深度极限学习机 delm
文章浏览阅读466次。首先，3D游戏建模师，这个工作首先是个劳动密集的工作，当中不仅仅是建模，贴图，其中美术流程在时间上占了1/2。还有一半时间你是在做法线做低模做uv，这些工作完全是体力活，靠熟练度你可以做的比较好。而这些技术流程，本质上是为了妥协计算机机能不足，或者满足当世代游戏美术流程而产生的，随着计算机发展，这些流程会逐渐降低所占的比重。其次，3d建模处于整个游戏流程的末端环节，成为3d建模师，并不是可以完全了解整个游戏制作流程的，更多的乐趣来自于你依托于原画创建出了令人信服的3d角色后的成就感。再次，3d建模薪水回_次时代3d建模师的缺口
文章浏览阅读1.2k次。《python组合数据类型》由会员分享，可在线阅读，更多相关《python组合数据类型(73页珍藏版)》请在人人文库网上搜索。1、Python语言程序设计,第6章 组合数据类型,组合数据类型概述,序列类型,计算机不仅对单个变量表示的数据进行处理，更多情况，计算机需要对一组数据进行批量处理。一些例子包括： 给定一组单词python, data, function, list, loop，计算并输出每..._元组是包含0个或多个数据项的不可变序列
文章浏览阅读630次，点赞8次，收藏10次。SAP EXCEL上传如何实现指定读取某一个sheet页（ALSM_EXCEL_TO_INTERNAL_TABLE）_raise_exception" saplalsmex" bzw. lalsmexu01 alsm_excel_to_internal_table