https://leetcode.com/problems/longest-palindromic-subsequence
Given a string s, find the longest palindromic subsequence's length in s. You may assume that the maximum length of s is 1000.
Example 1:
Input:
Input:
"bbbab"Output:
4One possible longest palindromic subsequence is "bbbb".
Example 2:
Input:
Input:
"cbbd"Output:
2One possible longest palindromic subsequence is "bb".
X. Brute Force - DFS
- O(2^n) Brute force. If the two ends of a string are the same, then they must be included in the longest palindrome subsequence. Otherwise, both ends cannot be included in the longest palindrome subsequence.
int longestPalindromeSubseq(string s) {
return longestPalindromeSubseq(0,s.size()-1,s);
}
int longestPalindromeSubseq(int l, int r, string &s) {
if(l==r) return 1;
if(l>r) return 0; //happens after "aa"
return s[l]==s[r] ? 2 + longestPalindromeSubseq(l+1,r-1, s) :
max(longestPalindromeSubseq(l+1,r, s),longestPalindromeSubseq(l,r-1, s));
}
Let X[0..n-1] be the input sequence of length n and L(0, n-1) be the length of the longest palindromic subsequence of X[0..n-1].
If last and first characters of X are same, then L(0, n-1) = L(1, n-2) + 2.
Else L(0, n-1) = MAX (L(1, n-1), L(0, n-2)).
Else L(0, n-1) = MAX (L(1, n-1), L(0, n-2)).
lps(seq, 0, n-1)
X. DFS+ cache: O(n^2) Memoization
https://leetcode.com/problems/longest-palindromic-subsequence
public int longestPalindromeSubseq(String s) { int n = s.length(); int[][] dp = new int[n][n]; char[] c = s.toCharArray(); for (int i = 0; i < n; i++) { dp[i][i] = 1; for (int j = i-1; j >= 0; j--) { if (c[j] == c[i]) { dp[j][i] = dp[j + 1][i - 1] + 2; } else { dp[j][i] = Math.max(dp[j+1][i], dp[j][i-1]); } } } return dp[0][n-1]; }
X. DP 2 - bottom row to top row - along diagonal
https://discuss.leetcode.com/topic/78603/straight-forward-java-dp-solution
otherwise,
http://www.cnblogs.com/grandyang/p/6493182.html
X.
X.
https://discuss.leetcode.com/topic/78630/evolve-from-brute-force-to-dp
Different solution: http://massivealgorithms.blogspot.com/2014/07/longest-palindromic-substring-set-2.html
Read full article from Dynamic Programming | Set 12 (Longest Palindromic Subsequence) | GeeksforGeeks
int lps(char *seq, int i, int j){ // Base Case 1: If there is only 1 character if (i == j) return 1; // Base Case 2: If there are only 2 characters and both are same if (seq[i] == seq[j] && i + 1 == j) return 2; // If the first and last characters match if (seq[i] == seq[j]) return lps (seq, i+1, j-1) + 2; // If the first and last characters do not match return max( lps(seq, i, j-1), lps(seq, i+1, j) );}
Top bottom recursive method with memoization
public int longestPalindromeSubseq(String s) {
return helper(s, 0, s.length() - 1, new Integer[s.length()][s.length()]);
}
private int helper(String s, int i, int j, Integer[][] memo) {
if (memo[i][j] != null) {
return memo[i][j];
}
if (i > j) return 0;
if (i == j) return 1;
if (s.charAt(i) == s.charAt(j)) {
memo[i][j] = helper(s, i + 1, j - 1, memo) + 2;
} else {
memo[i][j] = Math.max(helper(s, i + 1, j, memo), helper(s, i, j - 1, memo));
}
return memo[i][j];
}
X. DP
How we fill the dp array: diagonal by diagonal, len++
--->
^
|
https://www.youtube.com/watch?v=U4yPae3GEO0
https://discuss.leetcode.com/topic/78603/straight-forward-java-dp-solution
otherwise,
How we fill the dp array: diagonal by diagonal, len++
--->
^
|
https://www.youtube.com/watch?v=U4yPae3GEO0
https://discuss.leetcode.com/topic/78603/straight-forward-java-dp-solution
dp[i][j]: the longest palindromic subsequence's length of substring(i, j)State transition:dp[i][j] = dp[i+1][j-1] + 2 if s.charAt(i) == s.charAt(j)otherwise,
dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1])Initialization: dp[i][i] = 1
Increasing distance between i and j may be better.
public int longestPalindromeSubseq(String s) {
int len=s.length();
int[][] dp=new int[len][len];
for (int i=0;i<len;i++)
dp[i][i]=1;
for (int d=1;d<len;d++) {
for (int i=0;i<len-d;i++) {
int j=i+d;
if (s.charAt(i)==s.charAt(j)) dp[i][j]=2+dp[i+1][j-1];
else dp[i][j]=Math.max(dp[i][j-1], dp[i+1][j]);//\\
}
}
return dp[0][len-1];
} static int lps(String seq) { int n = seq.length(); int i, j, cl; int L[][] = new int[n][n]; // Create a table to store results of subproblems // Strings of length 1 are palindrome of lentgh 1 for (i = 0; i < n; i++) L[i][i] = 1; // Build the table. Note that the lower diagonal values of table are // useless and not filled in the process. The values are filled in a // manner similar to Matrix Chain Multiplication DP solution (See // http://www.geeksforgeeks.org/archives/15553). cl is length of // substring for (cl=2; cl<=n; cl++) { for (i=0; i<n-cl+1; i++) { j = i+cl-1; if (seq.charAt(i) == seq.charAt(j) && cl == 2) L[i][j] = 2; else if (seq.charAt(i) == seq.charAt(j)) L[i][j] = L[i+1][j-1] + 2; else L[i][j] = max(L[i][j-1], L[i+1][j]); } } return L[0][n-1]; }
一道区间DP，更新没什么好说的，但需要注意两个for循环的遍历顺序。递推式：
//dp[j][i] 表示在区间[j,i]之间的最长回文，可断
s[j] == s[i]: dp[j][i] = dp[j+1][i-1] + 2;
//没有最新的回文生成，所以沿用旧的回文长度
s[j] != s[i]: dp[j][i] = Math.max(dp[j+1][i],dp[j][i-1]);public int longestPalindromeSubseq(String s) { int n = s.length(); int[][] dp = new int[n][n]; char[] c = s.toCharArray(); for (int i = 0; i < n; i++) { dp[i][i] = 1; for (int j = i-1; j >= 0; j--) { if (c[j] == c[i]) { dp[j][i] = dp[j + 1][i - 1] + 2; } else { dp[j][i] = Math.max(dp[j+1][i], dp[j][i-1]); } } } return dp[0][n-1]; }
X. DP 2 - bottom row to top row - along diagonal
https://discuss.leetcode.com/topic/78603/straight-forward-java-dp-solution
dp[i][j]: the longest palindromic subsequence's length of substring(i, j)State transition:dp[i][j] = dp[i+1][j-1] + 2 if s.charAt(i) == s.charAt(j)otherwise,
dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1])Initialization: dp[i][i] = 1 public int longestPalindromeSubseq(String s) {
int[][] dp = new int[s.length()][s.length()];
for (int i = s.length() - 1; i >= 0; i--) {
dp[i][i] = 1;
for (int j = i+1; j < s.length(); j++) {
if (s.charAt(i) == s.charAt(j)) {
dp[i][j] = dp[i+1][j-1] + 2;
} else {
dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);
}
}
}
return dp[0][s.length()-1];
}- O(n^2) time, O(n) space dp. In #3, the current row is computed from the previous 2 rows only. So we don't need to keep all the rows.
int longestPalindromeSubseq(string s) {
int n = s.size();
vector<int> v0(n), v1(n,1), v(n), *i_2=&v0, *i_1=&v1, *i_=&v;
for(int i=2;i<=n;i++) {//length
for(int j=0;j<n-i+1;j++)//start index
i_->at(j) = s[j]==s[i+j-1]?2+i_2->at(j+1):max(i_1->at(j),i_1->at(j+1));
swap(i_1,i_2);
swap(i_1,i_); //rotate i_2, i_1, i_
}
return i_1->at(0);
}http://www.cnblogs.com/grandyang/p/6493182.html
int longestPalindromeSubseq(string s) { int n = s.size(), res = 0; vector<int> dp(n, 1); for (int i = n - 1; i >= 0; --i) { int len = 0; for (int j = i + 1; j < n; ++j) { int t = dp[j]; if (s[i] == s[j]) { dp[j] = len + 2; } len = max(len, t); } } for (int num : dp) res = max(res, num); return res; }
解法II 动态规划（Dynamic Programming）
问题转化为求s与reversed(s)的最长公共子序列
public int longestPalindromeSubseq(String s) {
int size = s.length();
int[][] dp = new int[size + 1][size + 1];
for (int i = 1; i <= size; i++) {
for (int j = 1; j <= size; j++) {
if (s.charAt(i - 1) == s.charAt(size - j)) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
}
}
}
int ans = s.length() > 0 ? 1 : 0;
for (int m = 0; m < size; m++) {
ans = Math.max(dp[m][size - m] * 2, ans);
if (m > 0) ans = Math.max(dp[m - 1][size - m] * 2 + 1, ans);
}
return ans;
}X.
Top bottom recursive method with memoization
public int longestPalindromeSubseq(String s) {
return helper(s, 0, s.length() - 1, new Integer[s.length()][s.length()]);
}
private int helper(String s, int i, int j, Integer[][] memo) {
if (memo[i][j] != null) {
return memo[i][j];
}
if (i > j) return 0;
if (i == j) return 1;
if (s.charAt(i) == s.charAt(j)) {
memo[i][j] = helper(s, i + 1, j - 1, memo) + 2;
} else {
memo[i][j] = Math.max(helper(s, i + 1, j, memo), helper(s, i, j - 1, memo));
}
return memo[i][j];
}X.
https://discuss.leetcode.com/topic/78630/evolve-from-brute-force-to-dp
- O(2^n) Brute force. If the two ends of a string are the same, then they must be included in the longest palindrome subsequence. Otherwise, both ends cannot be included in the longest palindrome subsequence.
int longestPalindromeSubseq(string s) {
return longestPalindromeSubseq(0,s.size()-1,s);
}
int longestPalindromeSubseq(int l, int r, string &s) {
if(l==r) return 1;
if(l>r) return 0; //happens after "aa"
return s[l]==s[r] ? 2 + longestPalindromeSubseq(l+1,r-1, s) :
max(longestPalindromeSubseq(l+1,r, s),longestPalindromeSubseq(l,r-1, s));
}
Brute force solution, O(N^3):
The obvious brute force solution is to pick all possible starting and ending positions for a substring, and verify if it is a palindrome. There are a total of C(N, 2) such substrings (excluding the trivial solution where a character itself is a palindrome).
The obvious brute force solution is to pick all possible starting and ending positions for a substring, and verify if it is a palindrome. There are a total of C(N, 2) such substrings (excluding the trivial solution where a character itself is a palindrome).
Read full article from Dynamic Programming | Set 12 (Longest Palindromic Subsequence) | GeeksforGeeks
