1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public int longestPalindromeSubseq(String s) {
Integer[][] memo = new Integer[s.length()][s.length()];
return helper(s.toCharArray(), 0, s.length() - 1, memo);
}
private int helper(char[] sArray, int left, int right, Integer[][] memo) {
if (left > right) {
return 0;
}
if (left == right) {
return 1;
}
if (memo[left][right] != null) {
return memo[left][right];
}
if (sArray[left] == sArray[right]) {
return memo[left][right] = helper(sArray, left + 1, right - 1, memo) + 2;
}
return memo[left][right] = Math.max(helper(sArray, left + 1, right, memo),
helper(sArray, left, right - 1, memo));
}
}
|
上面是recursion + memoization的解法. 这个比较容易想出来. 思路就是两个指针在两头. 如果它们指向的char相同, 那么我们就需要求[left + 1, right - 1]框起来的LPS即可, 求到的结果加上2就ok了. 如果二者不同, 我们要么是不要left指向的char, 要么是不要right指向的char. 那为什么不能两个都不要呢? 因为这种情况会被包含在我们之前的操作中. 因为left和right都不要构成的substring是和只不要left和只不要right构成的substring的substring. 因此该情况是被包含的. 递归函数求的就是某个substring中最长的LPS.
时间复杂度: O(n^2) left可能的数字有[0, n - 1]. 如果left == 0, right有n - 1种选择, 如果left == 1, right有n - 2种选择, 以此类推. 因此是O(n^2)的情况. 我们用memo存, 每种情况只会经历一次, 因此是O(N^2)
空间复杂度: O(n^2) 因为用了memo.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public int longestPalindromeSubseq(String s) {
int[][] memo = new int[s.length()][s.length()];
char[] sArray = s.toCharArray();
for (int i = memo.length - 1; i >= 0; i--) {
memo[i][i] = 1;
for (int j = i + 1; j < memo[0].length; j++) {
if (sArray[i] == sArray[j]) {
memo[i][j] = memo[i + 1][j - 1] + 2;
} else {
memo[i][j] = Math.max(memo[i + 1][j], memo[i][j - 1]);
}
}
}
return memo[0][memo[0].length - 1];
}
}
|
根据上面的recursion写出的dp答案. 此时的dp依赖左侧或者下侧的答案. 对角线的值是1, 对角线左侧的值为0. 因此我们一开始遇到对角线的时候单独处理.
时间复杂度: O(N^2)
空间复杂度: O(N^2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public int longestPalindromeSubseq(String s) {
int[] memo = new int[s.length()];
char[] sArray = s.toCharArray();
for (int i = memo.length - 1; i >= 0; i--) {
memo[i] = 1;
int currDiag = 0;
for (int j = i + 1; j < memo.length; j++) {
int nextDiag = memo[j];
if (sArray[i] == sArray[j]) {
memo[j] = currDiag + 2;
} else {
memo[j] = Math.max(memo[j], memo[j - 1]);
}
currDiag = nextDiag;
}
}
return memo[memo.length - 1];
}
}
|
我们需要的左下角, 因此我们用一个变量记录这个左下角. 同时在我们更新当前的值之前, 这个位置装的是下一个位置需要的左下角的值, 因此我们也暂存一下. 这样1D dp就成了.
时间复杂度: O(n^2)
空间复杂度: O(n)
