-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathdynamicProgram.java
More file actions
37 lines (34 loc) · 827 Bytes
/
dynamicProgram.java
File metadata and controls
37 lines (34 loc) · 827 Bytes
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/**
*
*/
/**
* @author DELL
* Project Name: Java_learn
* Class Name: dynamicProgram
* date: 2019年10月17日
*/
public class dynamicProgram {
// 最长公共子序列(的长度)
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
String A = "1A2C3D4B56";
String B = "B1D23CA45B6A";
System.out.println(maxLengthOfCommonStrings(A, A.length(), B, B.length()));
}
public static int maxLengthOfCommonStrings(String s1, int n1, String s2, int n2){
int dp[][] = new int[n1+1][n2+1];
for(int i = 0; i < n1; i++){
for(int j = 0; j < n2; j++){
if(s1.charAt(i) == s2.charAt(j)){
dp[i+1][j+1] = dp[i][j] + 1;
} else{
dp[i+1][j+1] = Math.max(dp[i+1][j], dp[i][j+1]);
}
}
}
return dp[n1][n2];
}
}