<dp>求最长的公共子串
原创
300. Longest Increasing Subsequence
Given an unsorted array of integers, find the length of longest increasing subsequence.
Example:
Input: [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4. Note:
- There may be more than one LIS combination, it is only necessary for you to return the length.
- Your algorithm should run in O(n2) complexity.
题目大意：一个数组的最长上升子序列。
思路：这是一个动态规划问题，array[i]表示以array[i]为结尾的最长上升子序列的长度。动态回话方程:
array[i]= Math.max(array[i],1+array[j]);解法：
public int lengthOfLIS(int[] nums) {
if(nums == null|| nums.length ==0) return 0;
int [] array = new int[nums.length];
for (int i=0;i<array.length;i++){
array[i] = 1;
}
// array[i]表示以array[i]为结尾的最长上升子序列的长度。
for (int i = 1;i<nums.length;i++){
for (int j = 0;j<i;j++){
if (nums[j] < nums[i]){
array[i] = Math.max(array[i],1+array[j]);
}
}
}
int res = 1;
for (int i = 0;i<array.length;i++){
res = Math.max(res,array[i]);
}
return res;
}二.求最长的公共子串
给定两个字符串str1和str2，返回两个字符串的最长公共子串
例如：str1 = "1AB2345CD",str2 = "12345EF"
最长的子串是“2345”
解法一：
这是一个基本的动态规划解法，时间复杂度是O(N*M)，空间复杂度是O(N*M);
public static int [][] longestSubString(String str1,String str2){
char [] chars1 = str1.toCharArray();
char [] chars2 = str2.toCharArray();
int [][] dp = new int[chars1.length][chars2.length];
for (int i=0;i<str1.length();i++){
if (chars2[0] == chars1[i]){
dp[i][0] = 1;
}
}
for (int j = 1;j<str2.length();j++){
if (chars1[0] == chars2[j]){
dp[0][j] = 1;
}
}
for (int i = 1;i<chars1.length;i++){
for (int j = 1;j<chars2.length;j++){
if (chars1[i] == chars2[j]){
dp[i][j] = dp[i-1][j-1] + 1;
}
}
}
return dp;
}
public static String lcst1(String str1,String str2){
if (str1==null||str2==null||str1.equals("")||str2.equals("")){
return "";
}
int[][] dp = longestSubString(str1,str2);
int end = 0;
int max = 0;
for (int i = 0;i<str1.length();i++){
for (int j = 0;j<str2.length();j++){
if (dp[i][j]>max){
end = i;
max = dp[i][j];
}
}
}
return str1.substring(end-max+1,end+1);
}longestSubString（）函数获取dp数组：
1 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 1 0 0 0 0 0
0 0 2 0 0 0 0
0 0 0 3 0 0 0
0 0 0 0 4 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0 可以发现，最长的子数组长度是4，end变量找到合适的位置，然后取4个长度的字符串的长度即可。
解法二：
这是一个改进的方式，时间复杂度是O(N*M)，空间复杂度是O(1);
三.求最长的公共子序列
给定两个字符串str1和str2，返回两个字符串的最长公共子序列。
例如：str1 = "1A2C3D4B56" str2 = "B1D23CA45B6A"
"123456"或"12C4B6"，都是最长的公共子序列。
思路：LCS(m,n) 是S1[0...m]和S2[0...n]的最长公共子序列的长度。
那么存在两种情况：(从末尾到头)
S1[m] == S2[n]，则有：LCS(m,n) = 1 +LCS(m-1,n-1)
S1[m] != S2[n]，则有：LCS(m,n) =max(LCS(m-1,n),LCS(m,n-1))
求出公共子序列的长度如下：
public int LCS(String str1, String str2){
int[][] dp = new int[str1.length()+1][str2.length()+1];
for (int i = 1 ;i<=str1.length();i++){
for (int j = 1;j<=str2.length();j++){
if (str1.charAt(i-1) == str2.charAt(j-1)){
dp[i][j] = Math.max(dp[i][j],dp[i-1][j-1]+1);
}
else{
dp[i][j] = Math.max(dp[i][j-1],dp[i-1][j]);
}
}
}
return dp[str1.length()][str2.length()];
}假设：
String str1 = "13456778";
String str2 = "357486782";那么dp二维数组的输出如下：注意这里的dp定义的是（m+1）*（n+1）的，所以首行首列都是0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 1 1 1 1 1 1 1 1 1
0 1 1 1 2 2 2 2 2 2
0 1 2 2 2 2 2 2 2
0 1 2 2 2 2 3 3 3 3
0 1 2 3 3 3 3 4 4 4
0 1 2 3 3 3 3 4 4 4
0 1 2 3 3 4 4 4 5 5 现在仅仅求出的是公共子序列的长度，那么怎样才能将公共子序列求出来呢？？
- S1[i] != S2[j] ，且dp[i-1][j] = dp[i][j-1] 这种存在分支的情况，这里请都选择一个方向（之后遇到这样的情况，也选择相同的方向）
- 如果s1[i] == s2[j] 就跳转到dp[i - 1][j - 1],如果s1[i] != s1[j], 就向前找或向上找（只能一个方向）
代码实现如下所示：
int i = str1.length();
int j = str2.length();
while (i>0 && j>0){
if (str1.charAt(i-1) != str2.charAt(j-1)){
if (dp[i][j-1]>dp[i-1][j]){
j--;
}else{
i--;
}
} else { //S1[i] == S2[j], c[i - 1][j - 1]
result += str1.charAt(i-1);
i--;
j--;
}
}
return result;
}那么完整的求最长的公共子序列的代码如下
public String LCS(String str1, String str2){
String result = "";
int[][] dp = new int[str1.length()+1][str2.length()+1];
for (int i = 1 ;i<=str1.length();i++){
for (int j = 1;j<=str2.length();j++){
if (str1.charAt(i-1) == str2.charAt(j-1)){
dp[i][j] = Math.max(dp[i][j],dp[i-1][j-1]+1);
}
else{
dp[i][j] = Math.max(dp[i][j-1],dp[i-1][j]);
}
}
}
int i = str1.length();
int j = str2.length();
while (i>0 && j>0){
if (str1.charAt(i-1) != str2.charAt(j-1)){
if (dp[i][j-1]>dp[i-1][j]){
j--;
}else{
i--;
}
} else { //S1[i] == S2[j], c[i - 1][j - 1]
result += str1.charAt(i-1);
i--;
j--;
}
}
return result;
}原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。