给出一个字符串str，返回这个字符串的最长回文子序列长度

ゝ一纸荒年。 2022-10-10 12:32 22阅读 0赞

问题描述：

给出一个字符串str，返回这个字符串的最长回文子序列长度；比如：str = "a123b321c"

最长回文子序列是123b321，返回长度是7

解决方案：从暴力递归到动态规划演变，三种方案如下

1、暴力递归：

public class NanDaoPalindromeSum {
        public static void main(String[] args) {
            String s = "a123b321c";
            System.out.println(palindrome1(s));
        
        }
       
    
        /**
         * 暴力递归
         * @param s
         * @return
         */
        private static int palindrome1(String s) {
            if(s == null || s.length() == 0){
                return 0;
            }
            char[] str = s.toCharArray();
            return p1(str,0,str.length - 1);
        }
    
        private static int p1(char[] str, int L, int R) {
            if(L == R){
                return 1;
            }
            if(L == R - 1){
                return str[L] == str[R] ? 2:1;//相等是2，不等是1
            }
            int p1 = p1(str,L + 1,R - 1);
            int p2 = p1(str,L,R - 1);
            int p3 = p1(str,L + 1,R);
            int p4 = str[L] == str[R] ? (2 + p1(str,L + 1,R - 1)) : 0;
           // System.out.println("p1:"+p1+";P2:"+p2+";P3:"+p3+";P4:"+p4);
            return Math.max(Math.max(p1,p2),Math.max(p4,p3));//返回最大值
        }
    
    }

2、暴力递归到动态规划的过渡阶段：

2.1、图示分析：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA_size_16_color_FFFFFF_t_70][]

给出的字符串 String s = "a123b321c";   长度为 9 ；行是L，列是R，L<=R；当L==R时，对角线赋值1，挨着对角线问号（?）赋值为1或2（R 和R+1相等为2），右上角为最终返回值

2.2、核心代码：

public class NanDaoPalindromeSum {
        public static void main(String[] args) {
            String s = "a123b321c";
     
            System.out.println(palindrome2(s));
       
        }
      
        /**
         * 暴力递归到动态规划的过渡阶段
         * @param s
         * @return
         */
        private static int palindrome2(String s) {
            if(s == null || s.length() == 0){
                return 0;
            }
            char[] str = s.toCharArray();
            int N = str.length;
            int[][] dp = new int[N][N];
            dp[N - 1][N - 1] = 1;
            for(int i = 1;i < N - 1;i++){
                dp[i][i] = 1;
                dp[i][i + 1] = str[i] == str[i + 1] ? 2 : 1;//相等是2，不等是1
            }
            for(int L = N - 3;L >= 0;L--){
                for(int R = L + 2;R < N;R++){
                    int p1 = dp[L + 1][R - 1];
                    int p2 = dp[L][R - 1];
                    int p3 = dp[L + 1][R];
                    int p4 = str[L] == str[R] ? (2 + dp[L + 1][R - 1]) : 0;
                    dp[L][R] =  Math.max(Math.max(p1,p2),Math.max(p3,p4));
                }
            }
            return dp[0][N - 1];
        }
    
    
    }

3、标准的动态规划方案：

3.1、继续分析上图：某个格子位置是其左边和下边取最大值得到的，即6位置是从5和3位置中取最大值得到的，肯定不是其左下（2位置）的值，因此可以继续优化代码；

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA_size_16_color_FFFFFF_t_70 1][]

3.2、核心代码如下：

public class NanDaoPalindromeSum {
        public static void main(String[] args) {
            String s = "a123b321c";
          
            System.out.println(palindrome3(s));
        }
        /**
         * 动态规划
         * @param s
         * @return
         */
        private static int palindrome3(String s) {
            if(s == null || s.length() == 0){
                return 0;
            }
            char[] str = s.toCharArray();
            int N = str.length;
            int[][] dp = new int[N][N];
            dp[N - 1][N - 1] = 1;
            for(int i = 0;i < N - 1;i++){
                dp[i][i] = 1;//对角线赋值为1
                dp[i][i + 1] = str[i] == str[i + 1] ? 2 : 1;//对角线上面一层赋值，相等是2，不等是1
            }
    
            for(int L = N - 3;L >= 0;L--){
                for(int R = L + 2;R < N;R++){
                    dp[L][R] = Math.max(dp[L][R - 1],dp[L + 1][R]);//左和下左对比
                    if(str[L] == str[R]){//如果相等，继续往左下角遍历
                        dp[L][R] = Math.max(dp[L][R],(2 + dp[L + 1][R - 1]));
                    }
                }
            }
            return dp[0][N - 1];
        }
    
    }

3.3、三种方案的执行结果：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA_size_16_color_FFFFFF_t_70 2][]

4、三种方案的基本思想如下：

4.1、从上到下，从左到右，每个格子里的值就是需要返回的值，因此取最大值返回即可。

4.2、从尝试该动态规划，只需要把位置找对就行。

到此，该算法分享完毕，大家一定要多多练习，勤于思考，早日成为大牛！

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA_size_16_color_FFFFFF_t_70]: /images/20221005/fabf2a5338d54e91ad3de9d5bef0628f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA_size_16_color_FFFFFF_t_70 1]: /images/20221005/6f1cf8ef4f614c71bcbf934040e1fbdf.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA_size_16_color_FFFFFF_t_70 2]: /images/20221005/af39ef77d0b048f0b2e732b37b4afb39.png