[数据结构与算法]使用动态规划方法求最长回文串

动态规划

动态规划的思想就是，将一个大问题分解为规模更小的问题，这个小问题的解一定是可以直接求出的，并且原问题的最优解包含子问题的最优解。也就是说分治算法+贪婪算法！

寻找回文串

给定一个字符串s，找出s中的最大回文串。如
输入：s=“babad”
输出：“bab”（“aba”也可作为输出）

算法解析

设置一个二维数组 dp[i][j] ，存储字符串s的下标 i 到 j 之间的最大回文串长度。数组长度为dp[s.length()][s.length()]

1. 基础小问题的解：
   $$dp[i][i]=1;$$
   $$dp[i][i+1]=\{\begin{array}{ll}2& \text{if?s(i)?==?s(i+1)?}\\ 1& \text{if?s(i)?!=?s(i+1)?}\end{array}$$
2. 迭代关系：
   $$dp[i][j]=\{\begin{array}{ll}dp[i+1][j?1]+2,& \text{if?s(i)==s(i+1)?and?dp[i+1][j?1]=j?i?1}\\ max(dp[i+1][j],dp[i][j?1]),& \text{if?s(i)!=s(i+1)?}\end{array}$$
   PS: $dp[i+1][j?1]=(j?1)?(i+1)+1=j?i?1$ 即保证 i+1 , j-1 之间的字符都满足回文要求。

java 代码实现如下：

class Solution {
    public String longestPalindrome(String s) {
        // 使用动态规划思想
        if(s.length()==1){
            return s;
        }
        int[][] dp=new int[s.length()][s.length()];
        for(int i=s.length()-1;i>=0;i--){
            dp[i][i]=1; 
            if (i<s.length()-1){
                if(s.charAt(i)==s.charAt(i+1)){
                    dp[i][i+1]=2;
                }else{
                    dp[i][i+1]=1;
                }
                System.out.print(dp[i][i+1]);
            }
            
            for(int j=i+2;j<s.length();j++){
                if(s.charAt(i)==s.charAt(j) && dp[i+1][j-1]==j-i-1){    //必须里面也是回文
                    dp[i][j]=dp[i+1][j-1]+2;
                }else{
                    if(dp[i+1][j]>dp[i][j-1]){
                        dp[i][j]=dp[i+1][j];
                    }else{
                        dp[i][j]=dp[i][j-1];
                    }
                }    
            }
        }
        int v=dp[0][s.length()-1];
        if(v==1){  //回文长度为1，即都不相等
            return String.valueOf(s.charAt(0));  // 注意char与String转换
        }else{
            String res="";
            for(int i=0;i<s.length();i++){
                for(int j=i+1;j<s.length();j++){
                    if(dp[i][j]==v && (j-i+1)==v){
                        res=s.substring(i,j+1); //包头不包尾
                    }
                }
            }
            return res;  //最后必须有返回
        }    
    }
}