本文主要是介绍代码随想录第60天 | 647. 回文子串 、 516.最长回文子序列，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
一、前言
参考文献：代码随想录；
转眼间两个月已经过去，五一休息了三天，今天将要结束动态规划了。
今天的主题是用dp解决回文子串；
二、回文子串
1、思路：
我一开始就想用一维dp数组来解决这道题目，但是发现找不到关系，然后就尝试使用了一下暴力解法，感觉不错；
（1）暴力：
class Solution {
private:bool isPalindrom(string &s, int start, int end) {while (start < end) {if (s[start] != s[end]) {return false;}start++;end--;}return true;}
public:int countSubstrings(string s) {int count = 0;for (int i = 0; i < s.size(); i++) {for (int j = i; j < s.size(); j++) {if (isPalindrom(s, i, j)) {count++;}}}return count;}
};回到dp：
（1）递推公式 + 初始化：
我们需要判断改数组是不是回文串，所以我们定义的dp是bool类型，接着是我们需要一个边界来规定子串，这样才可以求出每个子串（这里顺带初始化了，全部都默认为false）：
vector<vector<bool>> dp(s.size(), vector<bool> (s.size(), false));（2）递推公式：
我们需要判断三个条件，当i == j时，很显然一个字母也是回文串，所以为false；
当 j - i == 1时，也是一个回文串，例如“aba”；
当 j - i > 1时，我们就需要利用dp数组来解决了，判断 i + 1 到 j - 1这个区间是不是回文串，才能判断是不是回文串
（3）遍历顺序：
看这个图片发现，新的状态是之前的状态得出来的，但是这个状态在新状态的左下角，所以需要从下往上，从左往右遍历；
2、整体代码如下：
class Solution {
public:int countSubstrings(string s) {// 1、定义dp数组+初始化// 在下标i与j之间的范围内，是否是回文子串vector<vector<bool>> dp(s.size(), vector<bool> (s.size(), false));int count = 0;// 2、遍历顺序，从下往上，从左往右for (int i = s.size() - 1; i >= 0; i--) {for (int j = i; j < s.size(); j++) {// 3、递推公式（三种情况）if (s[i] == s[j]) {if (j - i <= 1 ) {dp[i][j] = true;} else {dp[i][j] = dp[i + 1][j - 1];}}if (dp[i][j]) count++;}}return count;}
};三、最长回文序列
1、思路：
本题感觉有点小绕，所以我看了题解之后还是有点蒙蔽；
（1）dp数组定义：
可以看出这个与上一题目很像，但是求的是最长回文子串的长度，所以还是需要创建二维的int类型数组；
（2）递推公式：
分为两种情况，当 s[i] == s[j]时，就需要在原有的dp[i + 1][j - 1]的基础上加2；
（3）初始化：
首先要考虑当i 和j 相同的情况，从递推公式：dp[i][j] = dp[i + 1][j - 1] + 2; 可以看出 递推公式是计算不到 i 和j相同时候的情况。
所以要初始化这个对角线：
for (int i = 0; i < s.size(); i++) dp[i][i] = 1;（4）遍历顺序：
这里的遍历还是从下到上，从左到右
只是现在可以选择不连续的情况了，所以就如下（为什么不能把初始化的情况放到遍历中去？因为会越界，i == 0的时候就越界了）：
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]);}}}2、完整代码如下：
class Solution {
public:int longestPalindromeSubseq(string s) {// 1、初始化+定义dp数组vector<vector<int>> dp(s.size(), vector<int> (s.size(), 0));for (int i = 0; i < s.size(); i++) dp[i][i] = 1;// 2、遍历顺序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];}
};Study time 1h
Leave message:
Young people have changed the course of history time and time again.
年轻人一次又一次的改变了历史的进程。
这篇关于代码随想录第60天 | 647. 回文子串 、 516.最长回文子序列的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
