516. Longest Palindromic Subsequence

2019-11-06 07:50:39

字体：大中小

来源：转载

供稿：网友

超时代码，这道题就是一道DP问题，采用二维数组存储DP序列，

class Solution {public: int longestPalindromeSubseq(string s) { if(s.size()==0) return 0; int dp[1010][1010]={0}; for(int len=0;len<s.size();len++) { for(int left=0;left<s.size();left++) { int right=left+len;//[left,right] if(right<s.size()) { if(right==left) dp[left][right]=1; else { dp[left][right]=1; //int maxLength=0; map<char,vector<int>> func; for(int i=left;i<=right;i++) func[s[i]].push_back(i); int tempLeft=left; int temPRight=right; while(tempLeft!=tempRight) { char tempChar=s[tempLeft]; if(func[tempChar].size()>1) { if(dp[left][right]<(2+dp[tempLeft+1][func[tempChar].back()-1])) dp[left][right]=2+dp[tempLeft+1][func[tempChar].back()-1]; } tempLeft++; } } ///cout<<left<<" "<<right<<" "<<dp[left][right]<<endl; } } } return dp[0][s.size()-1]; }};

将代码做了简化，使得迭代次数减少。开始时left是从前到后都要遍历一次，而现在只考虑计数次数大于1的那些位置开头和结尾处的元素。==。发现依旧超时。

class Solution {public: int longestPalindromeSubseq(string s) { if(s.size()==0) return 0; int dp[1010][1010]={0}; for(int len=0;len<s.size();len++) { for(int left=0;left<s.size();left++) { int right=left+len;//[left,right] if(right<s.size()) { if(right==left) dp[left][right]=1; else { dp[left][right]=1; //int maxLength=0; map<char,vector<int>> func; for(int i=left;i<=right;i++) func[s[i]].push_back(i); for(map<char,vector<int>>::iterator it=func.begin();it!=func.end();it++) { if((it->second).size()>=2) { if(dp[left][right]<(2+dp[(it->second).front()+1][(it->second).back()-1])) dp[left][right]=(2+dp[(it->second).front()+1][(it->second).back()-1]); } } } //cout<<left<<" "<<right<<" "<<dp[left][right]<<endl; } } } return dp[0][s.size()-1]; }};

最后看了看discuss，发现DP方程其实可以更加优化。不需要寻找所有的[left,right]中出现次数大于1的位置。这样会出现大量重复计算。参考discuss的DP

class Solution {public: int longestPalindromeSubseq(string s) { if(s.size()==0) return 0; int dp[1010][1010]={0}; for(int len=0;len<s.size();len++) { for(int left=0;left<s.size();left++) { int right=left+len;//[left,right] if(right<s.size()) { if(right==left) dp[left][right]=1; else { dp[left][right]=1; //int maxLength=0; /*map<char,vector<int>> func; for(int i=left;i<=right;i++) func[s[i]].push_back(i); for(map<char,vector<int>>::iterator it=func.begin();it!=func.end();it++) { if((it->second).size()>=2) { if(dp[left][right]<(2+dp[(it->second).front()+1][(it->second).back()-1])) dp[left][right]=(2+dp[(it->second).front()+1][(it->second).back()-1]); } }*/ if(s[left]==s[right]) dp[left][right]=2+dp[left+1][right-1]; else dp[left][right]=dp[left+1][right]>dp[left][right-1]?dp[left+1][right]:dp[left][right-1]; } //cout<<left<<" "<<right<<" "<<dp[left][right]<<endl; } } } return dp[0][s.size()-1]; }};

上一篇：SSL 1644——取数字问题

下一篇：单例模式的几种写法