
LeetCode 516 最长回文子序列
题目描述
给定一个字符串 s
,找到其中最长的回文子序列。可以假设 s
的最大长度为 1000。
样例
样例输入1
bbbab
样例输出1
4
样例解释1
一个可能的最长回文子序列为 bbbb
。
样例输入2
cbbd
样例输出2
2
样例解释2
一个可能的最长回文子序列为 bb
。
算法与数据结构
动态规划
题解
再多看几道动态规划的题目,长老就要和大家分享微软、字节跳动等大公司笔试中的动态规划真题啦,所以大家一定要认真消化这几题哦。
最长回文子序列也是动态规划中的经典题目,这次不再是线性规划了,而是二维矩阵,不过理解起来也很容易。
回顾线性规划中,我们往往定义 dp[i]
为到 i 为止符合题目要求的解的值,而在二维动态规划中,我们往往定义 dp[i][j]
表示从 i 到 j 这一段中符合题目要求的解的值。
例如对于这道题,我们定义 dp[i][j]
表示字符串从 i 到 j 的子串中,最长子序列的长度。最终,dp[0][n - 1]
就是答案。
那么,状态转移呢?
为了得到 dp[i][j]
,我们可以考察 s[i]
和 s[j]
,如果这两个位置上的字符是一样的,那么显然,dp[i][j] = dp[i + 1][j - 1] + 2
。
如果这两个位置上的字符是不一样,那么,取 dp[i + 1][j]
和 dp[i][j - 1]
中较大的即可。
最后考虑初始条件,初始条件就是当长度为 1 时,自然成为回文序列,于是,dp[i][i] = 1
对任意的 i 成立。
但是在写代码的时候,我们需要注意,这里数组下标的循环并不能简单从 1 循环到 n:
for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { // TODO } }
通过简单比对样例输入输出可以很容易发现,状态转移并不是随着下标推进的,而是随着下标之间的距离(即 i 和 j 之间的距离)推进的:我们首先得到了 dp[i][i]
的值,都等于 1,也就是所有长度为 1 的子串,我们得到了它的最长回文子序列的长度,下面应该去计算所有长度为 2 的子串,再长度为 3 的子串……只有这样,我们比较 s[i]
和 s[j]
才是有意义的。
所以,一种常见的技巧就是以跨度 len
为外层循环,以下标 i
为内层循环,在循环内计算下标 j
。
for (int len = 1; len <= length; len++) { for (int i = 0; i + len - 1 < length; i++) { int j = i + len - 1; // TODO } }
完整代码
int length = s.length(); int[][] dp = new int[length][length]; for (int len = 1; len <= length; len++) { for (int i = 0; i + len - 1 < length; i++) { int j = i + len - 1; if (i == j) { dp[i][j] = 1; } else { 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][length - 1];
c++代码
int longestPalindromeSubseq(string s) {
int n = s.size();
vector< vector > dp(n, vector(n, 0));
for(int i=n-1; i>=0; i–){
dp[i][i] = 1;
for(int j=i+1; j>n; j++){
if(s[i] == s[j]){
// dp[i][j] = max(dp[i][j], dp[i+1][j-1]+2);
dp[i][j] = dp[i+1][j-1]+2;
}
else{
// dp[i][j] = max(dp[i][j], max(dp[i+1][j], dp[i][j-1]));
dp[i][j] = max(dp[i+1][j], dp[i][j-1]);
}
}
}
return dp[0][n-1];
}
@Robin代码块又出问题了- –