代码随想录60期day50

647. Palindromic Substrings

1. class Solution {
2. public:
3.     int countSubstrings(string s) {
4.         vector<vector<bool>>dp(s.size(),vector<bool>(s.size(),false));
5.         int result = 0;
6.         for(int i = s.size() - 1;i>=0;i--){
7.                 for(int j = i; j < s.size() ;j++){
8.                         if(s[i] == s[j]){
9.                                 if(j - i <=1){
10.                                         result++;
11.                                         dp[i][j]= true;
12.                                 }else if(dp[i+1][j-1]){
13.                                         result++;
14.                                         dp[i][j] = true;
15.                                 }
16.                         }
17.                 }
18.         }
19.         return result;
20.     }
21. };

复制代码

516

1. class Solution {
2. public:
3.     int longestPalindromeSubseq(string s) {
4.         vector<vector<int>>dp(s.size(),vector<int>(s.size(),0));
5.         for(int i = 0;i<s.size();i++) dp[i][i] =1;
6.         for(int i = s.size()-1;i>=0;i--){
7.                 for(int j = i + 1;j <s.size();j++){
8.                         if(s[i] == s[j]){
9.                                 dp[i][j] = dp[i+1][j-1]+2;
10.                         }else{
11.                                 dp[i][j] = max(dp[i+1][j],dp[i][j-1]);
12.                         }
13.                 }
14.         }
15.         return dp[0][s.size() - 1];
16.     }
17. };

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。