动态规划之最长公共子序列Java实现，规划最长序列java,public class

动态规划之最长公共子序列Java实现，规划最长序列java,public class

public class lcs {      /**      * @param args      */      public static void main(String[] args) {          String str1 = "ACCGGTCGAGTGCGCGGAAGCCGGCCGAA";          String str2 = "GTCGTTCGGAATGCCGTTGCTCTGTAAA";          int m = str1.length();          int n = str2.length();          int[][] c = new int[m+1][n+1];          System.out.println("lcs长度为"+lcs_len(str1,str2,c));          System.out.println("lcs序列为");          print_lcs(str1,str2,c);      }      public static int lcs_len(String str1,String str2,int[][] c){          if(str1==null||str2==null){              return -1;          }          int m = str1.length();          int n = str2.length();          for(int i =1;i<=m;i++){              c[i][0]=0;          }          for(int i=0;i<=n;i++){              c[0][i]=0;          }          for(int i =1;i<=m;i++){              for(int j =1;j<=n;j++){                  if(str1.charAt(i-1) == str2.charAt(j-1)){                      c[i][j] = c[i-1][j-1]+1;                  }                  else if(c[i-1][j]>=c[i][j-1]){                      c[i][j] = c[i-1][j];                  }                  else                       c[i][j] = c[i][j-1];              }          }          return c[m][n];      }      public static void print_lcs(String str1,String str2,int[][] c){          int k=0;          int i=str1.length();          int j=str2.length();          char[] temp = new char[c[i][j]];          while(c[i][j]>0){              if(str1.charAt(i-1) == str2.charAt(j-1)){                  temp[k] = str1.charAt(i-1);                  k++;                  i--;                  j--;              }              else if(c[i][j] == c[i-1][j])                  i--;              else                  j--;          }          for(int l=temp.length-1;l>=0;l--){              System.out.print(temp[l]);          }      }  }  

                                运行结果：

lcs长度为20lcs序列为GTCGTCGGAAGCCGGCCGAA