（1）理论部分：
（2）习题：
最长公共子串：
1 package month7.dp; 2 3 ///questionTerminal/181a1a71c7574266ad07f9739f791506 4 public class 最长公共子串 { 5public static void main(String[] args) { 6 最长公共子串 s = new 最长公共子串(); 7 String str1 = "ABABCGGG"; 8 String str2 = "BABCAH"; 9 System.out.println(s.Longest_Common_Substring(str1, str2));10}11 //将二维数组table[i][j]用来记录具有这样特点的子串——结尾同时也为为串x1x2⋯xi与y1y2⋯yj的结尾——的长度12public int Longest_Common_Substring(String str1, String str2) {13 int len1 = str1.length();14 int len2 = str2.length();15 int result = 0;16 int num = 0;17 int[][] table = new int[len1 + 1][len2 + 1];18 19 for (int i = 0; i <= len1; i++) {20 table[i][0] = 0;21 }22 for (int j = 0; j <= len2; j++) {23 table[0][j] = 0;24 }25 for (int i = 1; i <= len1; i++) {26 for (int j = 1; j <= len2; j++) {27 char c1 = str1.charAt(i-1);28 char c2 = str2.charAt(j-1);29 if (c1 != c2) {30 table[i][j] = 0;31 } else { // c1 == c232 table[i][j] = table[i - 1][j - 1] + 1;33 if (result < table[i][j]) {34result = table[i][j];35num = i;36System.out.println("-----" + num + "--");37 38 }39 }40 }41 }42 System.out.println(str1.substring(num - result , num ));43 return result;44}45 46public int Longest_Common_Substring2(String str1, String str2) {47 int len1 = str1.length();48 int len2 = str2.length();49 int result = 0;50 int num = 0;51 int[][] table = new int[len1 + 1][len2 + 1];52 for (int i = 0; i <= len1; i++) {53 for (int j = 0; j <= len2; j++) {54 if (i == 0 || j == 0) {55 table[i][j] = 0;56 } else if (str1.charAt(i - 1) != str2.charAt(j - 1)) {57 table[i][j] = 0;58 } else { // c1 == c259 table[i][j] = table[i - 1][j - 1] + 1;60 if (result < table[i][j]) {61result = table[i][j];62num = i;63System.out.println("-----" + num + "--");64 65 }66 }67 }68 }69 System.out.println(str1.substring(num - result , num ));70 return result;71}72 73 }
View Code
最长公共子序列：
1 package month7.dp; 2 3 public class 最长公共子序列 { 4int[][] b = new int[10][10]; 5public static void main(String[] args) { 6 最长公共子序列 s = new 最长公共子序列(); 7 // String str1 ="ABCD"; 8 // String str2 = "EACB"; 9 String str1 ="AGGTHAB";10 String str2 = "GXTXAYB";11 System.out.println(s.Longest_Common_Subsequence(str1, str2));12 s.print_lsc(str1.length(), str2.length(), str1);13 14}15//用二维数组c[i][j]记录串x1x2⋯xi与y1y2⋯yj的LCS长度16public int Longest_Common_Subsequence(String str1,String str2){17 int len1 = str1.length();18 int len2 = str2.length();19 int[][] table = new int[str1.length()+1][str2.length()+1];20 // int[][] b = new int[str1.length()+1][str2.length()+1];21 for(int i=0;i<=len1;i++){22 for(int j=0;j<=len2;j++){23 if(i==0 || j == 0){24 table[i][j] = 0;25 }else if(str1.charAt(i-1) != str2.charAt(j-1)){26 if(table[i-1][j] > table[i][j-1]){27table[i][j] = table[i-1][j];28b[i][j] = 1;29 }else{30table[i][j] = table[i][j-1];31b[i][j] = 2;32 }33 //table[i][j] = Math.max(table[i-1][j], table[i][j-1]);34 }else{ // Xi = Yj35 table[i][j] = table[i-1][j-1] +1;36 b[i][j] = 3;37 }38 }39 }40 int commomLength = table[len1][len2];41 return commomLength;42}43public void print_lsc(int i,int j,String str1){44 if(i ==0 || j == 0)45 return ;46 if(b[i][j] == 3){47 print_lsc(i-1, j-1, str1);48 System.out.print(str1.charAt(i-1));49 }else if(b[i][j] == 2){50 print_lsc(i, j-1, str1);51 }else if(b[i][j] == 1){52 print_lsc(i-1, j, str1);53 }54}55 }
View Code
最短编辑距离
1 package month7.dp; 2 3 ///masterlibin/p/5785092.html 4 public class 最短编辑距离 { 5public static void main(String[] args) { 6 最短编辑距离 s = new 最短编辑距离(); 7 8} 9 10public int editionDistance(String word1, String word2) {11 if (word1 == null || "".equals(word1)) {12 return word2.length();13 }14 if (word2 == null || "".equals(word1)) {15 return word1.length();16 }17 int len1 = word1.length();18 int len2 = word2.length();19 int[][] table = new int[len1 + 1][len2 + 1];20 for (int i = 0; i <= len1; i++) {21 table[i][0] = i;22 }23 for (int j = 0; j <= len2; j++) {24 table[0][j] = j;25 }26 for (int i = 1; i <= len1; i++) {27 for (int j = 1; j <= len2; j++) {28 char c1 = word1.charAt(i - 1);29 char c2 = word2.charAt(j - 1);30 if (c1 == c2) {31 table[i][j] = table[i - 1][j - 1];32 } else {33 int add = table[i][j - 1] + 1;34 int delate = table[i - 1][j] + 1;35 int edition = table[i - 1][j - 1] + 1;36 table[i][j] = Math.min(add, Math.min(delate, edition));37 }38 }39 }40 return table[len1][len2];41}42 43 }
View Code
