palindrome.java

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

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


/**
 * ID:1159
 * 动态规划
 * 数组用int则内存溢出
 * @author yhm
 *
 */
public class Palindrome {

	

	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		while (cin.hasNext()) {
			cin.nextInt();
			String str = cin.next();
			int r = solve(str);
			System.out.println(r);
		}

	}
	
	static int solve(String str){
		int size = str.length();
		short[][] result = new short[size][size];
		for(int right=0;right<size;right++){
			for(int left=right;left>=0;left--){
				if(left==right){
					result[left][right] = 0;
				}
			    else if(str.charAt(left)==str.charAt(right)){
					result[left][right] = result[left+1][right-1];
				}
				else{
					short temp1 = result[left+1][right];
					short temp2 = result[left][right-1];
					temp1++;
					temp2++;
					result[left][right] = temp1>temp2?temp2:temp1;
				}
			}
		}
		return result[0][size-1];		
	}	

}