LeetCode·516.最长回文子序列·动态规划
链接:https://leetcode.cn/problems/longest-palindromic-subsequence/solution/-by-xun-ge-v-y362/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
题目
思路
- 确定dp数组(dp table)以及下标的含义
dp[i][j]:字符串s在[i, j]范围内最长的回文子序列的长度为dp[i][j]。
- 确定递推公式
在判断回文子串的题目中,关键逻辑就是看s[i]与s[j]是否相同。
- 如果s[i]与s[j]相同。
- 那么dp[i][j] = dp[i + 1][j - 1] + 2;
- 如果s[i]与s[j]不相同,说明s[i]和s[j]的同时加入 并不能增加[i,j]区间回文子串的长度,那么分别加入s[i]、s[j]看看哪一个可以组成最长的回文子序列。
- 加入s[j]的回文子序列长度为dp[i + 1][j]。
- 加入s[i]的回文子序列长度为dp[i][j - 1]。
- 那么dp[i][j]一定是取最大的,即:dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
代码如下:
if (s[i] == s[j]) {
dp[i][j] = dp[i + 1][j - 1] + 2;
} else {
dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
}
- dp数组如何初始化
首先要考虑当i 和j 相同的情况,从递推公式:dp[i][j] = dp[i + 1][j - 1] + 2; 可以看出 递推公式是计算不到 i 和j相同时候的情况。
所以需要手动初始化一下,当i与j相同,那么dp[i][j]一定是等于1的,即:一个字符的回文子序列长度就是1。
其他情况dp[i][j]初始为0就行,这样递推公式:dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]); 中dp[i][j]才不会被初始值覆盖。
memset(dp, 0, sizeof(dp));
for (int i = 0; i < len; i++) dp[i][i] = 1;
- 确定遍历顺序
从递推公式dp[i][j] = dp[i + 1][j - 1] + 2 和 dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]) 可以看出,dp[i][j]是依赖于dp[i + 1][j - 1] 和 dp[i + 1][j],
也就是从矩阵的角度来说,dp[i][j] 下一行的数据。所以遍历i的时候一定要从下到上遍历,这样才能保证,下一行的数据是经过计算的。
代码
#define MAX(a, b) ((a) > (b) ? (a) : (b))
int longestPalindromeSubseq(char * s){
int len = strlen(s);
int dp[len][len];
memset(dp, 0, sizeof(dp));
for(int i = 0; i < len; i++)
dp[i][i] = 1;
for(int i = len-1; i >= 0; i--)
{
for(int j = i+1; j < len; j++)
{
if(s[i] == s[j])
dp[i][j] = dp[i+1][j-1] + 2;
else
dp[i][j] = MAX(dp[i+1][j], dp[i][j-1]);
}
}
return dp[0][len-1];
}
作者:xun-ge-v
链接:https://leetcode.cn/problems/longest-palindromic-subsequence/solution/-by-xun-ge-v-y362/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
相关文章
- 【LeetCode】最长递增子序列的个数 [M](动态规划)
- 【LeetCode】寻找两个正序数组的中位数 [H](二分法)
- 【LeetCode】最长公共子序列(动态规划)
- [LeetCode]Subsets II生成组合序列
- LeetCode_动态规划_困难_940.不同的子序列 II
- LeetCode_回溯_中等_491.递增子序列
- LeetCode·每日一题·891.子序列宽度之和·数学
- LeetCode·1143.最长公共子序列·动态规划
- LeetCode·674.最长连续递增序列·动态规划
- LeetCode·每日一题·946.验证栈序列·栈模拟
- [LeetCode] 659. Split Array into Consecutive Subsequences 将数组分割成连续子序列
- [LeetCode] 384. Shuffle an Array 数组洗牌
- [LeetCode] 43. Multiply Strings 字符串相乘
- [LeetCode] 128. Longest Consecutive Sequence 求最长连续序列
- [LeetCode] 727. Minimum Window Subsequence 最小窗口子序列
- leetcode算法: Find Bottom Left Tree Value