【Day59】代码随想录之动态规划_647回文子串_516最长回文子序列

动态规划理论基础

动规五部曲：

1. 确定dp数组 下标及dp[i] 的含义。
2. 递推公式：比如斐波那契数列 dp[i] = dp[i-1] + dp[i-2]。
3. 初始化dp数组。
4. 确定遍历顺序：从前到后or其他。
5. 打印。

出现结果不正确：

1. 打印dp日志和自己想的一样：递推公式、初始化或者遍历顺序出错。
2. 打印dp日志和自己想的不一样：代码实现细节出现问题。

1. 647回文子串

参考文档：代码随想录

分析：
判断一个字符串里面的有多少个回文串，需要二维dp数组，dp[i][j]表示字符串s的[i, j]之间有多少个回文字符串。当s[i] == s[j]的时候，有可能是回文串，i = j 或者 i和j相差一个时是回文串，如果i和j相差的大于1，则需要判断[i+1, j-1]是否是回文串了。而当s[i] != s[j]的时候，s的[i, j]肯定不是回文串，这也表示dp的初始化是false。

dp五部曲：

1. dp[i][j]含义：表示s[i, j]回文串的个数。统计一个字符串中回文串的个数，使用的是bool型的数组，如果dp[i][j] = true；那么最终的回文串个数加1，而不是记录有多少个回文子串。数组类型的设计也很有意思。
2. 递推公式：if(s[i] == s[j]) { if(j - i <= 1) {dp[i][j] = true; } else { dp[i][j] = dp[i+1][j-1]; } }
3. 初始化：dp[i][j] = false;
4. 遍历顺序：根据递推公式可以得知当前的dp[i][j]有可能需要借助左下方的dp[i+1][j-1]，所以遍历顺序是从下到上，先更新下面一行的数据；之后从左到右，先更新左侧的数据。

代码：

class Solution {
public:int countSubstrings(string s) {//dp[i]: 以i结尾的回文子串的个数tvector<vector<bool>> dp(s.size(), vector<bool>(s.size(), false));int sum = 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;sum++;}else if(dp[i+1][j-1]){dp[i][j] = true;sum++;}}}}return sum;}
};

2. 516最长回文子序列

参考文档：代码随想录

分析：
和上一题回文子串不同的地方在于这次的回文子序列不要求是连续的。所以还采用和上一题一样的方法使用二维的dp数组。但是为了更新回文子串的长度，需要将数组的类型设为int型。

dp五部曲：

1. dp[i][j]含义：表示字符串s中[i, j]之间的最长回文子序列。
2. 递推公式：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]);

4. 初始化：dp[i][i] = 1。其余为0。
5. 遍历顺序：根据递推公式，遍历顺序是从下到上，先把下一行的数据更新好，根据下一行的数据更新本行的数据；从左到右，先更新左侧的数据，根据左侧的数据更新本位置的数据。

代码：

class Solution {
public:int longestPalindromeSubseq(string s) {//返回最长回文串的长度，数组类型是int型vector<vector<int>> dp(s.size(), vector<int>(s.size(), 0));//初始化for(int i = 0; i < s.size(); i++) dp[i][i] = 1;//更新dpfor(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];}
};