LintCode刷题笔记-- LongestCommonSquence
标签:动态规划
题目描述:
Given two strings, find the longest common subsequence (LCS).
Your code should return the length of LCS.
解题思路:
这一题是非常经典的动态规划问题,在解题思路上可以按照经典的动态规划的解法,这是在系统学习动态规划之后第一个解决的LintCode上的问题:
1.子问题划分
给出两个字符串的A,B,两个字符串长度分别为lenA,lenB,求出两个字符串的LCS:
这划分为子问题:A.subString(0,0) 与B的LCS,在此基础上A.subString(0,1)与B的LCS,依次类推,可以得到A.subString(0,lenA-2), A.subString(0,lenA-1) 与B的LCS。 按照A的方法也同样可以对B在长度上进行分解。这样可以形成字符串A与B长度为lenA*lenB的矩阵,此矩阵为记录状态的“备忘录”。
2.初始状态的定义
对于LCS矩阵的初始状态,对于第一行与第一列相对应的意义为,A与B的第一个元素作为一个长度为1的字符串与对方是否存在公共字符,若存在,所在位置坐标已经后续坐标全部置为1.
3.问题与子问题解的关系
dp[i][j]:字符串的A的子串dp(0,i)与字符串B的子串dp(0,j)之间LCS的长度
dp[i][j]的取值:当A[i] == B[j],A(0,i)与B(0,j)之间的LCS会较比A(0,i-1)与B(0,j-1)多1,因为多了1位公共字符,LCS的长度自然会增加1。
当A[i]!=B[j], A(0,i)与B(0,j)之间的LCS会选择先前公共子串更多的部分作为下一步求解
4.边界条件
当达到A,B两者的最大长度时结束
5.参考代码:
public int longestCommonSubsequence(String A, String B) {
int lenA = A.length();
int lenB = B.length(); if(lenA == 0 || lenB == 0){
return 0;
} int[][] dp = new int[lenA][lenB]; if(A.charAt(0)==B.charAt(0)){
dp[0][0] = 1;
} for(int i = 1; i < lenA; i++){
if(B.charAt(0)==A.charAt(i)){
dp[i][0] = 1;
}else{
dp[i][0] = dp[i-1][0];
}
}
for(int j = 1; j < lenB; j++){
if(A.charAt(0)==B.charAt(j)){
dp[0][j] = 1;
}else{
dp[0][j] = dp[0][j-1];
}
} for(int i = 1; i<lenA; i++){
for(int j = 1; j<lenB; j++){
dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
if(A.charAt(i) == B.charAt(j)){
dp[i][j] = dp[i-1][j-1]+1;
} }
}
return dp[lenA-1][lenB-1];
}
最新文章
- angular源码分析:angular中$rootscope的实现——scope的一生
- 关于mongodb的复合索引新功能
- CentOS 6.5安装Apache
- Linux的awk命令
- polling 和 long polling 工作原理
- php curl 抓去远程页面内容
- Boostrap栅格系统
- 8-14-Exercise
- jQuery仿苏宁易购导航
- EasyUI TextBox的keypress
- 浅析ThreadLocal
- ZJOI2017 Day1
- 在本地搭建play-with-docker
- Python入门-数据类型
- docker学习-----docker可视化portainer
- MyEclipse has detected that less than 5% of
- NodeJs递归删除非空文件夹
- 《汇编语言 基于x86处理器》第十章 - 运行一个 16位实地址汇编程序
- Linux下替代grep高效文本搜索工具
- iOS开发--设置UIButton