agtc.java

PKU中一些数据结构基本算法题的java实现

package PKU.DP;
import java.util.Scanner;


/**
 * ID:3356
 * 动态规划
 * @author yhm
 *
 */
public class AGTC {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);

		while (cin.hasNext()) {
			cin.nextInt();
			String a = cin.next();
			cin.nextInt();
			String b = cin.next();
			int r = solve(a, b);
			System.out.println(r);
		}		
	}
	
	static int solve(String a, String b){
		int sa = a.length();
		int sb = b.length();
		int[][] m = new int[sa+1][sb+1];
		for(int i=0;i<=sa;i++){
			m[i][0] = i;
		}		
		for(int j=0;j<=sb;j++){
			m[0][j] = j;
		}

		for(int i=1;i<=sa;i++){
			for(int j=1;j<=sb;j++){
				int c = a.charAt(i-1)==b.charAt(j-1)?0:1;
				int temp1 = m[i-1][j] + 1;
				int temp2 = m[i][j-1] + 1;
				int temp3 = m[i-1][j-1] + c;
				int min = Math.min(temp1, temp2);
				min = Math.min(min, temp3);
				m[i][j] = min;
			}	
		}
		return m[sa][sb];
	}

}