Coding Caprice - dynamic programming13

647. 回文子串

class Solution {
public:int countSubstrings(string s) {int s_len = s.size();vector<int> dp{0};int out(1);for(int i=1; i<s_len; ++i){out++;vector<int> dq{i};if(s[i]==s[i-1]){dq.push_back(i-1);out++;}for(int j:dp){if(j>0&&s[j-1]==s[i]){dq.push_back(j-1);out++;}}swap(dp, dq);}return out;}
};

• 搞笑了

516. 最长回文子序列

class Solution {
public:int longestPalindromeSubseq(string s) {if(s.size()==1){return 1;}if(s.size()==2){return s[0]==s[1]?2: 1;}int len = s.size();vector<vector<int>> dp(len, vector<int> (len, 0));for(int i=0; i<len; ++i){dp[i][i] = 1;if(i+1>=len){break;}if(s[i] == s[i+1]){dp[i][i+1] = 2;}else{dp[i][i+1] = 1;}}for(int j=2; j<len; ++j){for(int i=0; i<len; ++i){if(i+j>=len){break;}if(s[i]==s[i+j]){dp[i][i+j] = dp[i+1][i+j-1] + 2;}else{dp[i][i+j] = max(dp[i+1][i+j], dp[i][i+j-1]);}}}return dp[0].back();}
};