【代码随想录算法训练Day52】LeetCode 647. 回文子串、LeetCode 516.最长回文子串

Day51 动态规划第十三天

LeetCode 647. 回文子串

dp数组的含义：i到j的子串是否是回文的，是的话dp[i][j]=1
递推公式：if(s[i]==s[j])
i ==j 一个元素 是回文的
|i-j|==1 两个元素 是回文的
j-i>1 判断dp[i+1][j-1]
初始化：全部初始化成false
遍历顺序：从左到右 从下往上

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){res++;dp[i][j]=true;}else if(dp[i+1][j-1]){res++;dp[i][j]=true;}}}}return res;}
};

LeetCode 516.最长回文子串

dp数组的含义：[i,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])
初始化：dp[i][i]=1 其余无所谓，初始化为0
遍历顺序：从左到右 从下往上

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;elsedp[i][j]=max(dp[i+1][j],dp[i][j-1]);}}return dp[0][s.size()-1];}
};

动态规划结束啦！