字符串最优匹配_人工智能DP算法

和大家分享分享，匹配基本都能通过。
import java.io.*;
import java.util.*;
class ValueOf_BestMathing{
private int value ;//当前数组元素值
private int pre_i = 0,pre_j = 0;//当前数组元素值是由谁得来

public ValueOf_BestMathing(int value){
this.value = value;
}
public void setValue(int vaule){
this.value = value;
}
public void setPre_iAndPre_j(int i,int j){
pre_i = i;
pre_j = j;
}
public int getValue(){
return value;
}
public int getPre_i(){
return pre_i;
}
public int getPre_j(){
return pre_j;
}
}
public class StringBestMatching{
private ValueOf_BestMathing[][] elem;//动态程序设计表
private String str1="" ;
private String str2="" ;
private BufferedReader  buf ;
private LinkedList<Character> list_str1;
public StringBestMatching(){
//输入两个字符串
 buf = new BufferedReader(new InputStreamReader(System.in));
  try{
   System.out.println("短字符串：");
    str1 = buf.readLine();
   System.out.println("长字符串：");
    str2 = buf.readLine();
  }
  catch(IOException e){
   e.printStackTrace();
  }
  elem = new ValueOf_BestMathing[str1.length()+1][str2.length()+1];
}
public void complete_Elem(){
//数组第一行第一列初始化
for(int i=0;i<str2.length()+1;i++){
   elem[0][i] = new ValueOf_BestMathing(i);
  }
  for(int j=0;j<str1.length()+1;j++){
   elem[j][0] = new ValueOf_BestMathing(j);
  }
for(int i = 1;i<str1.length()+1;i++){
for(int j = 1;j<str2.length()+1;j++){
if(str1.charAt(i-1) == str2.charAt(j-1)){
elem[i][j] = new ValueOf_BestMathing(elem[i-1][j-1].getValue());
elem[i][j].setPre_iAndPre_j(i-1,j-1);
}
else{
//求出(i,j-1) (i-1,j-1) (i-1,j)的最小值
ValueOf_BestMathing temp=elem[i][j-1].getValue()<
elem[i-1][j].getValue()?elem[i][j-1]:elem[i-1][j];
temp = elem[i-1][j-1].getValue()<temp.getValue()?elem[i-1][j-1]:temp;
if(temp == elem[i-1][j-1]){
elem[i][j] = new ValueOf_BestMathing(temp.getValue()+2);
elem[i][j].setPre_iAndPre_j(i - 1,j - 1);
}
else if(temp == elem[i][j-1]){
elem[i][j] = new ValueOf_BestMathing(temp.getValue()+1);
elem[i][j].setPre_iAndPre_j(i,j-1);
}
else{
elem[i][j] = new ValueOf_BestMathing(temp.getValue()+1);
elem[i][j].setPre_iAndPre_j(i-1,j);
}
}
}
}
}
public void Maybe_BestMatching(){
int i = str1.length();
int j = str2.length();
list_str1 = new LinkedList<Character>();
for(char c:str2.toCharArray())
list_str1.add('*');
while(i>0){
while(j>0){
if(elem[i][j].getPre_i()<i){
list_str1.set(j-1,str1.charAt(i-1));
i = elem[i][j].getPre_i();
j = elem[i][j].getPre_j();
}
else{
         j--;
}
}
}
System.out.println(str2);
Iterator<Character> iterator = list_str1.iterator();
  while(iterator.hasNext()){
   System.out.print(iterator.next());
  }
}
public static void main(String[] args){
StringBestMatching matching = new StringBestMatching();
  //填充数组elem
  matching.complete_Elem();
  matching.Maybe_BestMatching();
}
}