LC516. 最长回文子序列

class Solution {
    	public static int longestPalindromeSubseq(String s) {
            //常规操作
		if (s == null || s.length() == 0) {
			return 0;
		}
		if (s.length() == 1) {
			return 1;
		}
		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;//奇数
			dp[i][i + 1] = str[i] == str[i + 1] ? 2 : 1;//如果相等就是偶数
		}
        //从后向前看
		for (int i = N - 3; i >= 0; i--) {
			for (int j = i + 2; j < N; j++) {
				dp[i][j] = Math.max(dp[i][j - 1], dp[i + 1][j]);//要i位置或者要j位置
				if (str[i] == str[j]) {//如果i和j位置相等，同时移动
					dp[i][j] = Math.max(dp[i][j], dp[i + 1][j - 1] + 2);
				}
			}
		}
		return dp[0][N - 1];
	}
}
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