commonsubsequence.java

来自「PKU中一些数据结构基本算法题的java实现」· Java 代码 · 共 47 行

package PKU.DP;

import java.util.Scanner;

/**
 * ID:1458
 * 动态规划
 * 
 * @author yhm
 *
 */
public class CommonSubsequence {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		while(true){
			String a = cin.next();
			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];
		int i=0,j=0;

		for(i=1;i<=sa;i++){
			for(j=1;j<=sb;j++){
				if(a.charAt(i-1)==b.charAt(j-1)){
					m[i][j] = m[i-1][j-1]+1;
				}
				else{
					m[i][j] = Math.max(m[i-1][j], m[i][j-1]);
				}
			}	
		}
		return m[sa][sb];
	}
}