POJ1159,Palindrome

Description

Input

Output

Sample Input

5
Ab3bd

Sample Output

2

Source

</pre></p><p><pre name="code" class="java">import java.util.Arrays;
import java.util.Scanner;

public class POJ1159_ieayoio {
	static String s;

	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		while (cin.hasNext()) {
			int le = cin.nextInt();
			s = cin.next();
			short[][] f = new short[le + 5][le + 5];
			for (int i = 0; i < f.length; i++) {
				Arrays.fill(f[i], (short) 0);
			}
			for (int i = 1; i <= le; i++) {
				f[0][i] = (short) (le - i + 1);
			}
			for (int i = 1; i <= le; i++) {
				f[i][le + 1] = (short) i;
			}
			for (int i = 1; i <= le; i++)
				for (int j = le; j >= i; j--) {
					if (s(i) == s(j))
						f[i][j] = f[i - 1][j + 1];
					else {
						f[i][j] = (short) Math.min(f[i - 1][j] + 1,
								f[i][j + 1] + 1);
					}
				}
			int min = Integer.MAX_VALUE;
			for (int i = 1; i <= le - 1; i++) {
				if (min > f[i][i + 1])
					min = f[i][i + 1];
			}
			for (int i = 1; i <= le; i++) {
				if (min > f[i][i])
					min = f[i][i];
			}
			System.out.println(min);

		}
	}

	static char s(int i) {
		return s.charAt(i - 1);
	}
}

题目大意：求一个字符串最少添加几个字符可以变成回文串

我的思路就是f[i][j]表示左端数第i个字符，左端数在i右端的第j个字符，不过我开始只是觉得和最长公共子序列很像，没想到另一种方法就是求这个字符串和它逆串的最长公共子序列，然后再用总长度减去最长公共子序列的长度即为所求

POJ1159,Palindrome,布布扣,bubuko.com

POJ1159,Palindrome

原文：http://blog.csdn.net/ieayoio/article/details/38379435