算法思想
dp[i][j]表示[i,j]范围内的子串是否是回文子串
if(s[i]==s[j])
if(j-1<=1) //如果i==j和i+1==j两种情况
dp[i][j] = true;
else
dp[i][j] = dp[i+1][j-1]
//遍历顺序，因为依赖于左下角dp[i+1][j-1]的值，因此是从下往上，从左往右遍历
class Solution {
public:
int countSubstrings(string s) {
//[i,j]是否是回文
vector<vector<bool>> dp(s.size(), vector<bool> (s.size(),false));
int result=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-1<=i)
{
dp[i][j]=true;
result++;
}
else if(dp[i+1][j-1])
{
dp[i][j] =true;
result++;
}
}
}
}
return result;
}
};
算法思想：
动态规划
dp[i][j]表示【i，j】的最长回文子序列
if s[i] == s[j]
dp[i][j] = dp[i+1][j] +2;
else
dp[i][j] = min(dp[i-1][j], dp[i][j-1])
初始化
dp[i][i]=1
遍历顺序：从下往上，从左往右
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+1][j], dp[i][j-1]);
}
}
}
return dp[0][s.size()-1];
}
};
