647.?回文子串
思路：
這道題的難點在于如何確定dp數(shù)組的含義以及遞推關系哪廓〕鹾妫可以將i、j分別指向一個字符串的首位哆料，如果兩者是相同的就返回true吗铐，否則返回false，下一個字符串就可以在此字符串的基礎上繼續(xù)比較兩個端點處的值即可典阵。dp[i][j]：[i,j]區(qū)間內(nèi)的字符串是否是回文字串，是的話為true萄喳，否則為false。遞推關系：如果s[i]==s[j]充坑，有三種情況：1染突、i==j，此時dp[i][j]一定是true也榄，2司志、如果j-i==1，此時也一定是true囚霸，3激才、如果j-i>1，需要考慮dp[i+1][j-1]（里面的一個字符串）是否為true瘸恼，是的話dp[i][j]才是true。初始化：為了遞推關系的簡單东帅，所有元素初始化為false。遍歷順序：根據(jù)遞推關系邓夕，i需要從后向前阎毅，j從前向后点弯。
代碼：
class Solution {
public:
? ? int countSubstrings(string s) {
? ? ? ? vector<vector<bool>> dp(s.size(),vector<bool>(s.size(),false));
? ? ? ? int res=0;
? ? ? ? for(int i=s.size()-1;i>=0;i--)
? ? ? ? {
? ? ? ? ? ? for(int j=i;j<s.size();j++)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? if(s[i]==s[j])
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? if(j-i<=1)
? ? ? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? ? ? dp[i][j]=true;
? ? ? ? ? ? ? ? ? ? ? ? res++;
? ? ? ? ? ? ? ? ? ? }else
? ? ? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? ? ? if(dp[i+1][j-1]==true)
? ? ? ? ? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? ? ? ? ? dp[i][j]=true;
? ? ? ? ? ? ? ? ? ? ? ? ? ? res++;
? ? ? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? return res;
? ? }
};
516.?最長回文子序列
思路：
這道題的解題思路與上面一道題大致相同抢肛，dp[i][j]：區(qū)間[i,j]內(nèi)最長回文子序列的長度是dp[i][j]碳柱。遞推關系：如果s[i]==s[j]熬芜，最長子序列的長度dp[i][j]=dp[i+1][j-1]+2；如果不相等瑞侮，那就比較s[i]與s[j-1]以及s[i+1]與s[j]鼓拧，取二者的最大值即可。初始化：所有元初始化為0钮糖，同時由遞推關系可知酌住，i==j的情況是無法計算的，所以還要額外初始化一下消痛。遞推關系：i從大到小祭示，j從小到大。
代碼：
class Solution {
public:
? ? int longestPalindromeSubseq(string s) {
? ? ? ? vector<vector<int>> dp(s.size(),vector<int>(s.size(),0));
? ? ? ? for(int i=0;i<s.size();i++) dp[i][i]=1;
? ? ? ? for(int i=s.size()-1;i>=0;i--)
? ? ? ? {
? ? ? ? ? ? for(int j=i+1;j<s.size();j++)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? if(s[i]==s[j])
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? dp[i][j]=dp[i+1][j-1]+2;
? ? ? ? ? ? ? ? }else
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? dp[i][j]=max(dp[i][j-1],dp[i+1][j]);
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? return dp[0][s.size()-1];
? ? }
};
