1. /**
    2.  * 可以采用样本对应模型和范围尝试模型
    3.  * 方式1：样本对应模型：
    4.  * 基于上个题目  “求两个字符串的最长子序列长度”
    5.  * 一个字符串和与其逆序串 的最长公共子序列长度
    6.  * 即为一个字符串的最长回文子序列长度
    7.  * 所以：longestCommonSubsequence(str, reverse);即为结果
    8.  * 方式2：范围尝试模型：
    9.  * L-R 上的最长回文子序列长度
    10.  * 尝试讨论LR的情况
    11.  * 最长回文子序列长度
    12.  */
    13. // 测试链接：https://leetcode.com/problems/longest-palindromic-subsequence/
    14. public class Code01_PalindromeSubsequence {
    16.     // 方式2：基于范围尝试模型  暴力递归
    17.     public static int lpsl1(String s) {
    18.         if (s == null || s.length() == 0) {
    19.             return 0;
    20.         }
    21.         char[] str = s.toCharArray();
    22.         return process(str, 0, str.length - 1);
    23.     }
    25.     // str[L..R]最长回文子序列长度返回
    26.     public static int process(char[] str, int L, int R) {
    27.         // 讨论边界条件
    28.         if (L == R) { // 只有一个字符
    29.             return 1;
    30.         }
    31.         if (L == R - 1) {  // 只有两个字符
    32.             return str[L] == str[R] ? 2 : 1;
    33.         }
    34.         // L-R上最长回文子序列的可能性
    35.         // 可能性1：最长回文子序列既不以L开头，也不以R结尾， eg: a12321b    x L x R
    36.         int p1 = process(str, L + 1, R - 1);
    37.         // 可能性2：最长回文子序列以L开头，不以R结尾，      eg: 12321b     √ L x R
    38.         int p2 = process(str, L, R - 1);
    39.         // 可能性3：最长回文子序列不以L开头，以R结尾，      eg: a12321     x L √ R
    40.         int p3 = process(str, L + 1, R);
    41.         // 可能性4：最长回文子序列以L开头，以R结尾，        eg: a123er21a  √ L √ R
    42.         int p4 = str[L] != str[R] ? 0 : (2 + process(str, L + 1, R - 1));
    43.         return Math.max(Math.max(p1, p2), Math.max(p3, p4));
    44.     }
    46.     // 方式1：暴力递归-》动态规划
    47.     public static int lpsl2(String s) {
    48.         if (s == null || s.length() == 0) {
    49.             return 0;
    50.         }
    51.         char[] str = s.toCharArray();
    52.         int N = str.length;
    53.         int[][] dp = new int[N][N];
    54.         // 先填写右下角的
    55.         dp[N - 1][N - 1] = 1;
    56.         // 填写对角线部分
    57.         for (int i = 0; i < N - 1; i++) {
    58.             // 对角线
    59.             dp[i][i] = 1;
    60.             // 第二条对角线
    61.             dp[i][i + 1] = str[i] == str[i + 1] ? 2 : 1;
    62.         }
    63.         // 由于剩下的某个点，分别依赖，左边的，下边的，和左下角的三个位置。 从下向上依次填写。N-3开始，以为 N-1和N-2都填写过了
    64.         for (int L = N - 3; L >= 0; L--) {
    65.             for (int R = L + 2; R < N; R++) {  // 从L+2位置开始，前两条对角线L和L+1已经填写过了
    66.                   // 根据递归过程获取位置依赖
    67. //                int p1 = dp[L + 1][R - 1];
    68. //                int p2 = dp[L][R - 1];
    69. //                int p3 = dp[L + 1][R];
    70. //                int p4 = str[L] != str[R] ? 0 : 2 + dp[L + 1][R - 1];
    71. //                dp[L][R] = Math.max(Math.max(p1,p2),Math.max(p3,p4));
    73.                 // 位置优化版本  ？位置依赖 它的左位置，下位置，以及左下位置。三者取最大值，向前推，？左位置怎么求出来的，也是根据这三个位置，
    74.                 // 中最大值求出来的，下位置同理。因此，？位置，只需要依赖左位置和下位置即可，左位置和下位置一定比左下位置大，因此只需要左位置和
    75.                 // 和下位置进行比较求最大值即可。于是优化如下：
    76.                 dp[L][R] = Math.max(dp[L][R - 1], dp[L + 1][R]);
    77.                 if (str[L] == str[R]) {
    78.                     dp[L][R] = Math.max(dp[L][R], 2 + dp[L + 1][R - 1]);
    79.                 }
    80.             }
    81.         }
    82.         return dp[0][N - 1];
    83.     }
    85.     //#######################################################################################3
    86.     // 方式1： 采用样本对应模型，基于最长公共子序列题
    87.     public static int longestPalindromeSubseq1(String s) {
    88.         if (s == null || s.length() == 0) {
    89.             return 0;
    90.         }
    91.         if (s.length() == 1) {
    92.             return 1;
    93.         }
    94.         char[] str = s.toCharArray();
    95.         char[] reverse = reverse(str);
    96.         return longestCommonSubsequence(str, reverse);
    97.     }
    99.     // 最长公共子序列
    100.     public static int longestCommonSubsequence(char[] str1, char[] str2) {
    101.         int N = str1.length;
    102.         int M = str2.length;
    103.         int[][] dp = new int[N][M];
    104.         dp[0][0] = str1[0] == str2[0] ? 1 : 0;
    105.         for (int i = 1; i < N; i++) {
    106.             dp[i][0] = str1[i] == str2[0] ? 1 : dp[i - 1][0];
    107.         }
    108.         for (int j = 1; j < M; j++) {
    109.             dp[0][j] = str1[0] == str2[j] ? 1 : dp[0][j - 1];
    110.         }
    111.         for (int i = 1; i < N; i++) {
    112.             for (int j = 1; j < M; j++) {
    113.                 dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
    114.                 if (str1[i] == str2[j]) {
    115.                     dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - 1] + 1);
    116.                 }
    117.             }
    118.         }
    119.         return dp[N - 1][M - 1];
    120.     }
    122.     // 字符串反转
    123.     public static char[] reverse(char[] str) {
    124.         int N = str.length;
    125.         char[] reverse = new char[str.length];
    126.         for (int i = 0; i < str.length; i++) {
    127.             reverse[--N] = str[i];
    128.         }
    129.         return reverse;
    130.     }
    132. //################################################################
    133.     // 绝对位置依赖，优化
    134.     public static int longestPalindromeSubseq2(String s) {
    135.         if (s == null || s.length() == 0) {
    136.             return 0;
    137.         }
    138.         if (s.length() == 1) {
    139.             return 1;
    140.         }
    141.         char[] str = s.toCharArray();
    142.         int N = str.length;
    143.         int[][] dp = new int[N][N];
    144.         dp[N - 1][N - 1] = 1;
    145.         for (int i = 0; i < N - 1; i++) {
    146.             dp[i][i] = 1;
    147.             dp[i][i + 1] = str[i] == str[i + 1] ? 2 : 1;
    148.         }
    149.         for (int i = N - 3; i >= 0; i--) {
    150.             for (int j = i + 2; j < N; j++) {
    151.                 dp[i][j] = Math.max(dp[i][j - 1], dp[i + 1][j]);
    152.                 if (str[i] == str[j]) {
    153.                     dp[i][j] = Math.max(dp[i][j], dp[i + 1][j - 1] + 2);
    154.                 }
    155.             }
    156.         }
    157.         return dp[0][N - 1];
    158.     }
    160. }