[leetcode-516-Longest Palindromic Subsequence]
2024-08-26 13:57:49
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:
"bbbab"
Output:
4
One possible longest palindromic subsequence is "bbbb".
Example 2:
Input:
"cbbd"
Output:
2
One possible longest palindromic subsequence is "bb"
思路:
参考:
动态规划解决。设立一个len行len列的dp数组。dp[i][j]表示字符串i~j下标所构成的子串中最长回文子串的长度。最后我们需要返回的是dp[0][len-1]的值。
dp数组这样更新:首先i指针从尾到头遍历,j指针从i指针后面一个元素开始一直遍历到尾部。一开始dp[i][i]的值都为1,如果当前i和j所指元素相等,说明能够加到i~j的回文子串的长度中,所以更新dp[i][j] = dp[i+1][j-1] + 2; 如果当前元素不相等,那么说明这两个i、j所指元素对回文串无贡献,则dp[i][j]就是从dp[i+1][j]和dp[i][j-1]中选取较大的一个值即可。
https://www.liuchuo.net/archives/3204
int longestPalindromeSubseq(string s)
{
int n = s.size();
vector<vector<int>>dp(n,vector<int>(n)); for(int i=n-;i>=;i++)
{
dp[i][i] = ;
for(int j = i+;j<n;j++)
{
if(s[i] == s[j]) dp[i][j] = dp[i+][j-]+;
else dp[i][j] = max(dp[i+][j] , dp[i][j-]);
}
}
return dp[][n-];
}
最新文章
- shell脚本重新挂载出问题的卷
- js检测手机摇一摇
- Controller
- WPF入门教程系列七——布局之WrapPanel与StackPanel(二)
- Binary Tree Vertical Order Traversal
- linux笔记三-------根目录相关说明
- Jenkins pipeline 入门到精通系列文章
- Android dex分包方案
- JavaScript DOM编程艺术第一章:JavaScript简史
- Android工具:延展图片NinePatch
- 简易google地图api调用
- 2007LA 3902 网络(树+贪心)
- UE32修改TAB键为空格键
- 把ipad作为电脑的第二显示器
- Python算法与数据结构--求所有子数组的和的最大值
- P1171 售货员的难题--搜索(剪枝)
- bzoj 2150
- linux用户和组管理,/etc/passwd 、/etc/shadow和/etc/group --学习
- geeksforgeeks-Array-Rotate and delete
- SPOJ - MATSUM 二维树状数组单点更新