思路：

以dp【i】表示以s【i】結尾的回文子串的個數，發現遞推公式推導不出來此路·不通

以dp【i】【j】表示s【i】到s【j】的回文子串的個數，遞推公式也推不出

正確 dp【i】【j】表示s【i】到s【j】是否為回文串

確定遞歸順序：

dp【i】【j】依賴于dp【i+1】【j-1】因此 i從后往前遍歷，j從前往后遍歷

則最后秩序統計矩陣上三角為true的個數

class Solution {
public:int countSubstrings(string s) {vector<vector<bool>>dp(s.size(),vector<bool>(s.size(),false));int ans=0;for(int i=s.size()-1;i>=0;i--){    //這里實際上只修改上三角矩陣的值 for(int j=i;j<s.size();j++){if(s[i]==s[j]){if((i-j)<=1){dp[i][j]=true;ans++;}else{if(dp[i+1][j-1]==true){dp[i][j]=true;ans++;}}}}}return ans;}
};

?思路：

由于是要判斷是否是回文，即要比較s【i】與s【j】顯然用二維數組定義是合適的

dp[i][j]表示s【i】到s【j】的最長回文子序列的長度

推導遞推公式

if(s[i]==s[j]){

j==i? ?dp[i][j]=1

j-i=1 dp[i][j]=2

j-i>1 dp[i][j]=dp[i+1][j-1]+2

}else{

j-i=1 dp[i][j]=1

j-i>1 dp[i][j]=dp[i+1][j-1]

注意：這里是錯的 考慮bba 或者abb 這里應該是dp【i】【j】=max（dp【i】【j-1】，dp【i+1】【j】）

遍歷順序：

與上題一樣 i從大到小 j從小到大

初始化：直接初始化為1

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

最后一天動態規劃 開心！！！！！