FilesExpand file tree

 master

/

dynamicProgram.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

37 lines (34 loc) · 827 Bytes

 master

/

dynamicProgram.java

Copy path

Top

File metadata and controls

• Code
• Blame

37 lines (34 loc) · 827 Bytes

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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];

}

}