騰訊2017暑期實習生算法題-構造回文（動态規劃）

構造回文

時間限制：1秒

空間限制：32768K

給定一個字元串s，你可以從中删除一些字元，使得剩下的串是一個回文串。如何删除才能使得回文串最長呢？

輸出需要删除的字元個數。

輸入描述:

輸入資料有多組，每組包含一個字元串s，且保證:1<=s.length<=1000.

輸出描述:

對于每組資料，輸出一個整數，代表最少需要删除的字元個數。

輸入例子1:

abcda

google

輸出例子1:

2

2`

題目連結（出自牛客網）

思路：

利用回文串的特點，想到将字元串逆轉後，“回文串”（不一定連續）相當于順序沒變，求原字元串和反串的最公共子序列的長度（經典動态規劃類型），然後用字元串的長度減去這個最大公共子串的長度就得到了最小删除的長度。

心得：其實這題不難，算是可以直接套模闆的，但是要會把構造回文串的題目意思正确的了解出來，将它轉化成動态規劃。

代碼：

import java.util.Scanner;
public class Main 
{
	public static void main(String[] args) 
	{
		Scanner sc=new Scanner(System.in);
		while(sc.hasNext())
		{
			String str=sc.nextLine().trim();
			char[] chs1=str.toCharArray();
			char[] chs2=new StringBuffer(str).reverse().toString().toCharArray();
			int n=chs1.length;
			int[][] dp=new int[n+1][n+1];
			int max=0;
			for(int i=1;i<=n;i++)
			{	
				for(int j=1;j<=n;j++)
				{
					if(chs1[i-1]==chs2[j-1])
						dp[i][j]= dp[i-1][j-1]+1;
					else
						dp[i][j]= Math.max(dp[i-1][j], dp[i][j-1]);
					max=Math.max(max, dp[i][j]);
				}
			}
			System.out.println(n-max);
		}
	}

}