給定一個(gè)字符串str丑掺，刪除部分字符使其變成回文串猪钮，問(wèn)最少刪除多少字符可以變成回文串，即最長(zhǎng)回文串胆建。（騰訊筆試題）
這個(gè)問(wèn)題可以進(jìn)行轉(zhuǎn)化:
將str進(jìn)行反轉(zhuǎn)烤低，得到str1，只需比較str和str1的最長(zhǎng)公共子序列即可笆载。求出最長(zhǎng)公共子序列之后扑馁，將str的長(zhǎng)度減去最長(zhǎng)公共子序列的長(zhǎng)度就是需要?jiǎng)h除的字符數(shù)。
采用動(dòng)態(tài)規(guī)劃的方法求最長(zhǎng)公共子序列凉驻。記字符串a(chǎn)（長(zhǎng)度為i）腻要，字符串b（長(zhǎng)度為j）的最長(zhǎng)公共子序列為c[i][j],用一個(gè)二維數(shù)組存放。于是有下面的遞推公式涝登。
image.png
java代碼(實(shí)現(xiàn)騰訊筆試題)
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Solution s = new Solution();
Scanner sc = new Scanner(System.in);
while(sc.hasNextLine()) {
System.out.println( s.getResult(sc.nextLine()) );
}
sc.close();
}
}
class Solution {
public int getResult(String s) {
StringBuilder s1 = new StringBuilder(s);
StringBuilder s2 = new StringBuilder(s).reverse();
return s.length() - LCS(s1, s2);
}
public int LCS(StringBuilder s1, StringBuilder s2) {
int m = s1.length();
int n = s2.length();
int[][] mutrix = new int[m + 1][n + 1];
for(int i = 1; i <= m; i++) {
for(int j = 1; j <= n; j++) {
if(s1.charAt(i - 1) == s2.charAt(j - 1))
mutrix[i][j] = mutrix[i - 1][j - 1] + 1;
else
mutrix[i][j] = Math.max(mutrix[i - 1][j], mutrix[i][j - 1]);
}
}
return mutrix[m][n];
}
}
c語(yǔ)言代碼（實(shí)現(xiàn)最長(zhǎng)公共子序列）(遞歸)
#include <stdio.h>
#include <string.h>
int c[200][200];
char x[200],y[200];
int max(int a,int b){
if(a>b) return a;
return b;
}
int lcs(int lenx,int leny){
if(lenx==0||leny==0) return 0;
if(x[lenx-1]==y[leny-1]) return lcs(lenx-1,leny-1)+1;
return max(lcs(lenx,leny-1),lcs(lenx-1,leny));
}
int main(){
scanf("%s%s",x,y);
int lenx,leny;
lenx = strlen(x);
leny = strlen(y);
printf("%d",lcs(lenx,leny));
return 0;
}
c語(yǔ)言代碼（實(shí)現(xiàn)最長(zhǎng)公共子序列）（利用二維數(shù)組）
#include <stdio.h>
#include <string.h>
int c[200][200];
int max(int a,int b){
if(a>b) return a;
return b;
}
int main(){
char x[200],y[200];
scanf("%s%s",x,y);
int lenx,leny,i,j;
lenx = strlen(x);
leny = strlen(y);
for(i=1;i<=lenx;i++){
for(j=1;j<=leny;j++){
if(x[i]==y[j]) c[i][j] = c[i-1][j-1]+1;
else c[i][j] = max(c[i][j-1],c[i-1][j]);
}
}
printf("%d",c[lenx][leny]);
return 0;
}
