算法学习-LPS最长回文子序列模板（JAVA实现）

本文最后更新于：May 13, 2023 pm

纸上得来终觉浅，绝知此事要躬行。路漫漫其修远兮，吾将上下而求索！知识是经过历史的巨人沉淀下来的，别总想着自己能够快速学会，多花点时间去看看，也许会发现些不同的东西。你能快速学会的、觉得简单的东西，对于别人来说也是一样的。人外有人，天外有天。当努力到达了一定的程度，幸运自会与你不期而遇。

目录

LPS最长回文子序列

子序列：不一定连续的n个字符。

字串：连续的n个字符。

状态方程

大致分析

对任意字符串，如果头和尾相同，那么它的最长回文子序列一定是去头去尾之后的部分的最长回文子序列加上头和尾；如果头和尾不同，那么它的最长回文子序列是去头的部分的最长回文子序列和去尾的部分的最长回文子序列的较长的那一个。

str[0…n-1]是给定的字符串序列，长度为n，假设f(0,n-1)表示序列str[0…n-1]的最长回文子序列的长度。

    1. 如果str的最后一个元素和第一个元素是相同的，则有：f(0,n-1)=f(1,n-2)+2；例如字符串序列“AABACACBA”，第一个元素和最后一个元素相同，其中f(1,n-2)表示红色部分的最长回文子序列的长度；
    1. 如果str的最后一个元素和第一个元素是不相同的，则有：f(0,n-1)=max(f(1,n-1),f(0,n-2))；例如字符串序列“ABACACB”，其中f(1,n-1)表示去掉第一个元素的子序列，f(0,n-2)表示去掉最后一个元素的子序列。

以”BBABCBCAB”为例：

代码实现

正常实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
import java.io.*;
import java.math.BigInteger;
import java.util.*;


/**
 * @Author DragonOne
 * @Date 2021/12/5 21:27
 * @墨水记忆 www.tothefor.com
 */
public class Main {
    public static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    public static BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
    public static StreamTokenizer cin = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    public static PrintWriter cout = new PrintWriter(new OutputStreamWriter(System.out));
    public static Scanner sc = new Scanner(System.in);

    public static int maxd = 10000+7;
    public static int INF = 0x3f3f3f3f;
    public static int mod = 998244353;
    public static char[] str = new char[maxd];
    public static int[][] dp = new int[2][maxd];


    public static void main(String[] args) throws Exception {

        String s=nextString();
        str = s.toCharArray();
        int len = s.length();
        for(int i = len - 1; i >= 0; i--) {
            dp[i][i] = 1;
            for(int j = i + 1; j < len; j++)
            {
                if(str[i] == str[j]) dp[i][j] = dp[i+1][j-1] + 2;
                else dp[i][j] = Math.max(dp[i][j-1],dp[i+1][j]);
            }
        }
        System.out.println(dp[0][len-1]);

        closeAll();
    }

    public static void cinInit(){
        cin.wordChars('a', 'z');
        cin.wordChars('A', 'Z');
        cin.wordChars(128 + 32, 255);
        cin.whitespaceChars(0, ' ');
        cin.commentChar('/');
        cin.quoteChar('"');
        cin.quoteChar('\'');
        cin.parseNumbers(); //可单独使用来还原数字
    }

    public static int log(int x){ //log方法是以2为底,求x的对数。java自带的log是以e为底的
        return (int) (Math.log(x)/Math.log(2));
    }

    public static int nextInt() throws Exception{
        cin.nextToken();
        return (int) cin.nval;
    }
    public static long nextLong() throws Exception{
        cin.nextToken();
        return (long) cin.nval;
    }
    public static double nextDouble() throws Exception{
        cin.nextToken();
        return cin.nval;
    }
    public static String nextString() throws Exception{
        cin.nextToken();
        return cin.sval;
    }
    public static void closeAll() throws Exception {
        cout.close();
        in.close();
        out.close();
    }

}

滚动数组优化

可以发现，计算第 i 行时只用到了第 i+1 行，这样我们便不需要 n 行，只需要2行即可。所以可以使用滚动数组进行空间优化。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
import java.io.*;
import java.text.SimpleDateFormat;
import java.util.*;


/**
 * @Author DragonOne
 * @Date 2021/12/5 21:27
 * @墨水记忆 www.tothefor.com
 */
public class Main {
    public static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    public static BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
    public static StreamTokenizer cin = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    public static PrintWriter cout = new PrintWriter(new OutputStreamWriter(System.out));
    public static Scanner sc = new Scanner(System.in);

    public static int maxd = 10000+7;
    public static int INF = 0x3f3f3f3f;
    public static int mod = 998244353;
    public static char[] str = new char[maxd];
    public static int[][] dp = new int[2][maxd];


    public static void main(String[] args) throws Exception {

        String s=nextString();
        str = s.toCharArray();
        int len = s.length();
        int cur = 0;
        for(int i = len - 1; i >= 0; i--) {
            cur ^= 1;
            dp[cur][i] = 1;
            for(int j = i + 1; j < len; j++)
            {
                if(str[i] == str[j]) dp[cur][j] = dp[cur^1][j-1] + 2;
                else dp[cur][j] = Math.max(dp[cur][j-1],dp[cur^1][j]);
            }
        }
        System.out.println(dp[cur][len-1]);
        closeAll();
    }

    public static void cinInit(){
        cin.wordChars('a', 'z');
        cin.wordChars('A', 'Z');
        cin.wordChars(128 + 32, 255);
        cin.whitespaceChars(0, ' ');
        cin.commentChar('/');
        cin.quoteChar('"');
        cin.quoteChar('\'');
        cin.parseNumbers();
    }
    public static int nextInt() throws Exception {
        cin.nextToken();
        return (int) cin.nval;
    }
    public static long nextLong() throws Exception {
        cin.nextToken();
        return (long) cin.nval;
    }
    public static double nextDouble() throws Exception {
        cin.nextToken();
        return cin.nval;
    }
    public static String nextString() throws Exception {
        cin.nextToken();
        return cin.sval;
    }
    public static void closeAll() throws Exception {
        cout.close();
        in.close();
        out.close();
    }
}