腾讯2017暑期实习生编程题 第一题

测试地址：https://www.nowcoder.com/questionTerminal/28c1dc06bc9b4afd957b01acdf046e69
问题：给定一个字符串s，你可以从中删除一些字符，使得剩下的串是一个回文串。如何删除才能使得回文串最长呢？
输出需要删除的字符个数。

image.png
思路：将字符串倒置后与原来的字符串比较，得到最大子串就是回文了。这样就变成最长公共子序列(LCS)问题。动态规划模拟推导过程即可。可以参考下边的链接学习
文本比较算法Ⅱ——Needleman/Wunsch算法

import java.util.Scanner;
public class Main{

    
public static void main(String[] args) {

        Scanner sc=new Scanner(System.in);
        while (sc.hasNext()) {
        String s1 = sc.nextLine();
            String s2 = new StringBuffer(s1).reverse().toString();
        int dp[][]=new int [s1.length()+1][s2.length()+1];
        for(int i=1;i<s1.length()+1;i++) {
            for(int n=1;n<s2.length()+1;n++) {
                if(s1.charAt(i-1)==s2.charAt(n-1)) {
                    dp[i][n]=dp[i-1][n-1]+1;
                }else {
                    dp[i][n]=dp[i-1][n]>dp[i][n-1]?dp[i-1][n]:dp[i][n-1];
                }
            }
        }
        System.out.println(s1.length()-dp[s1.length()][s2.length()]);
        
    }
        }
        
            
}