动态规划--回文串问题

1 回文子串

2 最长回文子串

3 分割回文串

4 分割回文串Ⅳ

5 分割回文串Ⅱ

6 最长回文子序列

7 让字符串成为回文字符串的最小插入次数

本文主要讲解几个经典的使用动态规划解决的回文串问题。

1 回文子串

https://leetcode.cn/problems/palindromic-substrings/

对于本题，其实最优的解法是中心扩展法，顾名思义，就是以一个字符或者两个字符为猜想回文串的中心字符，然后如果当前回文串的左边届前一个字符和右边界后一个字符相等的话，那么将这两个字符加入进来又能够组成新的回文串。

中心扩展法：

class Solution {
public:int countSubstrings(string s) {//中心扩展法int res = 0 , n = s.size(); for(int i = 0 ; i < n ; ++i){  //枚举每一个回文子串的中心点//1 以s[i]为中心，回文串的长度为奇数res++; //首先s[i] 本身是一个回文子串int left = i - 1 ,right = i + 1;while(left >= 0 && right < n){if(s[left] == s[right]) res++;else break;--left,++right; //尝试扩大区间，再将当前回文子串的左右两个字符加入进来，看是否还构成回文子串}//2 以s[i] 和 s[i+1]为中心，回文串的长度为偶数left = i , right = i + 1;while(left >= 0 && right < n){if(s[left] == s[right]) res++;else break;--left,++right;}}return res;}
};

虽然动态规划不是最优解，但是本题数据量不是很大，还是可以是用动态规划来解决。

对于一个回文串，他需要满足什么条件？

1 第一个字符和最后一个字符相同；

2 除掉第一个字符和最后一个字符的剩余子串是一个回文串；

第二个条件我们可以转换为子问题，那么我们只需要解决第一个条件，判断第一个字符和最后一个字符是否相同。

我们假设子串的第一个字符和最后一个字符的下标分别是 i 和 j ，那么判断子串 [i,j]是否为回文串就需要判断 s[i] 和 s[j] 是否相同，以及判断 [i+1,j-1] 这个区间是否为回文串。

但是这其中，可能 i == j 或者 i == j-1 ，那么 [i+1,j-1] 这个区间就是非法的，或者说是空串，而空串我们可以看成是回文串。

那么我们可以定义状态表示:

dp[i][j] 表示 s 的 [i,j] 子串是否为回文串。

状态转移方程:

根据上面的分析，要使 dp[i][j] == true ，必须要满足s[i] == s[j] 且 dp[i+1][j-1] 为true，那么转移方程如下:

dp[i][j] = (s[i] == s[j] && dp[i+1][j-1]);

细节问题：

初始化与填表：填表的时候我们需要考虑或者说填的值只有 j >= i 的位置，也就是只需要填对角线以及上半区间，剩余的位置都表示空串，而空串是回文子串，所以其他的位置我们都初始化为 true，同时对角线上的位置其实表示的是s[i] 单个字符，而一个字符的时候其实也是回文串，不需要额外的判断，那么我们可以将整张表初始化为 true ,然后从下往上填写每一行，行号为 i，每一行从第 i+1 列开始从左往右填。

返回值：要求的是回文子串的数量，其实就是dp表中所有的 j >= i 的位置中为true的位置的总数，由于我们在初始化的时候相当于已经将对角线的值都填好了true，那么我们可以初始化res = s.size() ，然后在填表过程中，填完之后如果为true，那么++res;

动态规划代码：

class Solution {
public:int countSubstrings(string s) {int n = s.size();vector<vector<bool>> dp(n,vector<bool>(n,true));int res = n;for(int i = n-1 ; i >= 0 ; --i){for(int j = i + 1 ; j < n ; ++j){dp[i][j] = (s[i] == s[j] && dp[i+1][j-1]);if(dp[i][j]) ++res;}}return res;}
};

2 最长回文子串

5. 最长回文子串 - 力扣（LeetCode）

题目解析：本题要求的是最长的回文子串，其实处理思想还是上一题一样，最优的解法还是中心扩展法，这里我们就不给出中心扩展法的代码了，我们直接讲解dp的思路。

动态规划的时候，我们还是通过dp表来枚举所有的子串是否为回文子串，当dp[i][j] 为true 的时候，那么该回文子串的长度就是 j - i + 1。那么我们可以先用一个dp表来预处理，在dp表填表的时候同时记录最大的长度以及此时的子串左边界。

动态规划思路与上题一致，只是在处理返回值的时候有区别，代码如下：

class Solution {
public:string longestPalindrome(string s) {int n = s.size();vector<vector<bool>> dp(n, vector<bool>(n, true));int res = 1 , left = 0;for (int i = n - 1; i >= 0; --i) {for (int j = i + 1; j < n; ++j) {dp[i][j] = (s[i] == s[j] && dp[i + 1][j - 1]);if (dp[i][j]){if(j - i + 1 > res){res =j - i + 1;left = i; }}}}return s.substr(left,res);}
};

3 分割回文串

131. 分割回文串 - 力扣（LeetCode）

题目解析：给定一个字符串，要求我们将字符串分割成一个一个的回文子串，返回所有的分割方案。本题还是需要使用上面的dp表进行预处理，先枚举出每一个子串是否为回文串，然后通过回溯算法进行分割。

本题其实重点并不是动态规划算法和回文串问题，主要是回溯算法的使用，同时也需要动态规划进行预处理。

class Solution {
public:void Split(const string&s , const vector<vector<bool>>&dp , int start, vector<string> split,vector<vector<string>>&res){//需要分割 [start,n-1] 的子串//如果start == n ，那么说明已经分割完了if(start == s.size()) res.push_back(move(split)); //说明已经拆分完了，同时拆分的结果保存在split中//判断start开始的所有子串中，是否有回文串，如果有，就尝试将其再次分割for(int i = start; i < s.size() ; ++i){if(dp[start][i]){split.push_back(s.substr(start,i - start + 1));Split(s,dp,i+1,split,res); //下一轮分割从 i+1 开始//判断完之后回退split.pop_back();}}}vector<vector<string>> partition(string s) {int n = s.size();vector<vector<bool>> dp(n, vector<bool>(n, true));for (int i = n - 1; i >= 0; --i) {for (int j = i + 1; j < n; ++j) {dp[i][j] = (s[i] == s[j] && dp[i + 1][j - 1]);}}//预处理完之后，开始分割//返回s的所有的分割方案，我们可以拆分成子问题//首先在 s 的前半部分找出一个回文串，将其拆分出来，然后再对剩余部分进行分割，而剩余部分的分割就是子问题//设计为回溯vector<vector<string>> res;vector<string> split; //用于保存当前栈帧的结果split.reserve(n);Split(s,dp,0,split,res);  //分割的是 [0,n-1]的串return res;}
};

4 分割回文串Ⅳ

1745. 分割回文串 IV - 力扣（LeetCode）

题目解析：我们需要将字符串 s 划分为三个子串，三个子串都是回文字符串，判断能否划分出来。本题的思路其实完全可以参考上一题，但是由于本题已经限制了分割之后的字串个数，且个数很小，仅为3，那么这个题其实比上一个题还要简单。

对于本题，最简单暴力的做法就是枚举，要将一个字符串划分为三个子串，只需要切割两次，也就是需要枚举两个边界，然后分别判断三个字串是否为回文串就行了。而判断三个子串是否为回文串，我们要保证高效率，避免进行重复判断，可以继续利用第一个题目的动态规划的思路，将所有字串是否为回文串放在dp表中保存起来。

那么代码如下：

class Solution {
public:bool checkPartitioning(string s) {int n = s.size();vector<vector<bool>> dp(n, vector<bool>(n, true));for (int i = n - 1; i >= 0; --i) {for (int j = i + 1; j < n; ++j) {dp[i][j] = (s[i] == s[j] && dp[i + 1][j - 1]);}}//枚举两个边界// [0,i],[i+1,j],[j+1,n-1]for(int i= 0; i < n - 2 ; ++i){for(int j = i + 1 ; j < n -1 ; ++j){if(dp[0][i] && dp[i+1][j] && dp[j+1][n-1]) return true;}}return false;}
};

5 分割回文串Ⅱ

132. 分割回文串 II - 力扣（LeetCode）

解析题目：题目需要我们将字符串 s 拆分成若干个子串，每个子串都需要是回文串，返回最少的分割次数。首先我们需要判断每一个子串是否是回文串，那么使用dp表预处理枚举所有的子串是否为回文串这一个步骤还是必须的。

而我们需要求的是最小的分割次数，首先我们需要判断整个字符串是不是回文串，如果当前字符串本身就是回文串了，那么不需要分割就是回文串，而如果字符串不是回文串，那么我们需要将其进行分割，而分割的规则是什么呢？首先分割出来的子串必须都是回文串，那么我们可以将字符串分割成两部分也就是两个子串，如果其中一个子串是回文串，另一个子串也是回文串，那么只需要分割一次就能完成，如果只有其中一个是回文串，另一个不是回文串，那么说明不是回文串的子串还需要继续分割，那么总的分割次数就是 1 + 非回文子串的分割次数。这样一来就转换为了子问题,可以用递归或者动态规划来解决。当然还有一种情况就是两个子串都不是回文串，那么此时的分割次数就是两个子串的分割次数再加1，不过这种情况显然不可能是最优的情况，我们不需要考虑。

那么按照我们的思路，就是在整个字符串的基础上，分割出一个回文子串，然后再去对剩余部分的子串进行回文串的分割。而这个回文子串如何选择呢？从前面进行分割还是从后面进行分割呢？其实两种都可以，只不过需要不同的状态表示。我们假设从后面进行分割，那么我们定义一个状态表示为：

dp[i] 表示将s的[0,i]区间进行回文串拆分，所需要的最小分割次数。

那么我们推导状态转移方程：

对于[0,i]的字符串，如果是一个回文串，那么dp[i] = 0 ,如果不是，那么我们可以尝试从后半部分先拆分出一个回文串，也就是找到一个 j ，满足[j,i] 子串是一个回文串，然后还需要将[0,j-1]的字符串区间继续进行回文串分割，我们需要的是最小的分割次数，那么需要[0,j-1]区间的分割次数最小，也就是 dp[j-1] ,那么总的分割次数就是dp[i] = dp[j-1] + 1 ，但是由于我们可能有多种方案能够在[0,i]的后半部分拆分出一个回文子串，那么这多种方案中，我们需要选择分割次数最小的回文串，也就是在 [j,i] 是回文串的情况下，dp[i] = min(dp[j-1]) + 1。

状态转移方程：

dp[i] = min(dp[j]) + 1 ([j,i] 是回文串)

那么如何判断[j,i]是回文串或者说 j 的取值如何选择呢？这就需要用到我们前面使用的预处理的结果了，预处理之后我们已经把所有子串是否为回文串的结果记录在一个表中了。

细节问题：

初始化的时候，dp[0] 表示的是第一个字符的子串，不需要分割就是回文串，所以dp[0] = 0;由于我们填表的时候需要求min，所以可以把dp表初始化为最大值。

填表顺序：从左往右填写dp表

返回值：需要返回的是将整个字符串s分割成若干个回文串的最小分割次数，那么返回的就是dp[n-1].

代码如下：

class Solution {
public:int minCut(string s) {int n = s.size();//预处理枚举所有的子串是否为回文串vector<vector<bool>> is(n,vector<bool>(n,true));for(int i = n-1 ; i >= 0 ; --i){for(int j = i +  1; j < n ; ++j){is[i][j] = s[i] == s[j] && is[i+1][j-1];}}vector<int>dp(n,0x3fffffff); //dp[i] 表示将[0,i]拆分成回文串所需的最少分割次数dp[0] = 0 ;for(int i = 1 ;i < n ; ++i){if(!is[0][i]){ //[0,i]不是回文串的时候才需要分割for(int j = 1 ; j <= i ; ++j){ //判断[j,i]是否回文，如果是，尝试将其分割if(is[j][i]){dp[i] = min(dp[j-1] + 1,dp[i]);}}} else dp[i] = 0 ;  //不需要划分}return dp[n-1];}
};

如果我们定义状态表示 dp[i] 为[i,n-1]的回文串分割的最少次数，那么我们就需要枚举从[i,n-1]子串的前半部分分割出一个回文子串，那么因为他的子问题就是[j,n-1]的会问分割的最少次数。

6 最长回文子序列

516. 最长回文子序列 - 力扣（LeetCode）

解析题目：首先本题需要求的是最长的回文子序列的长度，而子序列和子串的区别就类似于子序列和子数组的区别，子串要求必须是原字符串中的一个连续的区间，而子序列可以是不连续，只要保证相对顺序与原字符串中一样就行了。

我们先按照子序列问题的经验，定义状态表示为：dp[i] 表示以 s[i] 为结尾的最长回文子序列的长度，那么我们需要推导后续的状态，也就是是dp[i+x]，以s[i+x]为结尾的最长回文子序列的长度，如何形成一个新的回文子序列呢？我们可以在一个回文子序列的基础上，在其前面和后面加上相同的字符，那么形成的新序列也是一个回文子序列，但是我们如何根据前面的状态来推导dp[i+x]呢？我们需要知道dp[i] 的最长回文子序列的起始位置，然后才能够在其起始位置的前面去找到s[i+x]相同的字符，所以我们这个简单的状态定义是无法解决问题的，对应最长回文子序列所在的区间范围。

所以我们可以这样进行状态表示:

dp[i][j] 表示字符串 s 的[i,j] 区间内的最长回文子序列的长度。

那么我们接着来推导状态转移方程：

如何求出dp[i][j] 呢？有两种情况：1： s[i] == s[j] ，那么此时dp[i][j]的最长回文子序列一定包含s[i]和s[j]，为什么呢？这是一种贪心的思路，因为选择s[i]和s[j]之后，剩余的子序列的范围为[i+1,j-1]，而如果我们选择其他的s[x] == s[j]，x>i ，选择 x 和 j ，那么剩余的子序列的范围就是[x+1,j-1]，而[x+1,j-1]只是[i+1,j-1]的一个子区间，在[i+1，j-1]区间内可以尝试找到更长的回文子序列。

2：s[i] != s[j] ，说明[i,j]范围内的最长回文子序列一定不会同时包含s[i] 和 s[j] ，那么我们可以有三种情况：1 包含s[i],不包含s[j],dp[i][j-1] ，2 包含s[j],不包含s[i] ,dp[i+1][j]， 3 s[i]和s[j]都不包含,dp[i+1][j-1]，那么此时[i,j]范围内的最长回文子序列的长度就是这三种情况下的最长回文子序列的长度的最大值，也就是 dp[i][j] = max(dp[i+1][j],dp[i][j-1],dp[i+1][j-1]，但是我们可以想象，[i+1,j-1]这个范围是 [i+1,j] 和 [i,j-1] 的一个子区间，那么起始dp[i+1][j-1]的结果不会对dp[i][j]的结果产生应影响，所以 dp[i][j] = max(dp[i+1][j] , dp[i][j-1])。

那么综上，状态转移方程：

细节问题：

初始化：由于dp[i][j]需要用到dp[i+1][j] ，dp[i][j-1] 和dp[i+1][j-1] ，那么对于j == 0 和 j == n的时候，我们是需要手动初始化的，j==0的时候，表示的是[i,0]区间的最长回文子序列的长度，当i>0的时候，不存在，我们可以填0，当i==0的时候，表示s[0]这个字符，它本身就是回文子序列，所以dp[0][0] = 1; 而 i == n-1 的时候也是类似的，dp[n-1][j]表示的是[n-1,j]的最长回文子序列的长度，那么当 j < n-1 的时候，不存在这样的子序列，所以填0，而j==n-1的时候，表示的是s[n-1]，它本身就是一个回文子序列，所以dp[n-1][n-1] = 1; 那么综合而言，我们可以将整张dp表初始化为0，然后手动填写dp[0][0] = dp[n-1][n-1] = 0;

填表顺序:dp[i][j]需要用到dp[i+1][j] ，dp[i][j-1] 和dp[i+1][j-1]，那么我们需要从下往上填写每一行，从左往右填写每一列。

返回值：返回的是整个字符串的最长回文子序列的长度，也就是dp[0][n-1].

代码如下：

class Solution {
public:int longestPalindromeSubseq(string s) {int n = s.size();vector<vector<int>>dp(n,vector<int>(n));dp[0][0] = dp[n-1][n-1] = 1;for(int i = n - 1; i >= 0 ; --i){for(int j = i ; j < n ; ++j){if( i == j) {dp[i][j] = 1; //特殊处理continue;}if(s[i] == s[j]) dp[i][j] = 2 + dp[i+1][j-1];  //注意，这里dp[i+1][j-1]有可能不合法，但是他们填的值是0，不影响结果else dp[i][j] = max(dp[i+1][j] , dp[i][j-1]);}}return dp[0][n-1];}
};

本题还有一个很巧妙的解法：原字符串s，将原字符串进行翻转之后形成的字符串s1，根据回文子序列的定义，我们只需要求出s和s1的最长公共子序列的长度，那么就求出了最长的回文子序列的长度，这种思路会在我们的两个数组的dp问题中讲解。

7 让字符串成为回文字符串的最小插入次数

1312. 让字符串成为回文串的最少插入次数 - 力扣（LeetCode）

解析题目:我们需要对字符串s进行插入，使其变成回文字符串，返回最小的插入次数。

本题的分析思路和上一个题一样，定义状态表为:

dp[i][j] 表示是字符串s的[i,j]区间成为回文串的最小插入次数。

推导状态转移方程：

对于dp[i][j] ，如果s[i] == s[j] ，我们需要让s[i]和s[j]配对，这样插入次数是最少的，dp[i][j] = dp[i+1][j-1]，原因与上一题一样。

而如果 s[i] != s[j] ，意味着在[i,j]的左边或者右边必须要插入一个字符，如果在左边插入,就需要插入s[j]，那么此时插入的字符与s[j]配对，剩下的区间就是 [i,j-1]，我们还需要让[i,j-1]也是回文字符串，那么此时 dp[i][j] = 1 + dp[i][j-1] ，如果插入在右边，那么需要插入s[i]，此时剩余的区间就是[i+1,j]，我们需要让剩余的区间也是回文字符串，那么dp[i][j] = 1 + dp[i+1][j] ，而我们需要的是最少的次数，所以需要在这两种情况下取最小值 dp[i][j] = min(dp[i+1][j] , dp[i][j-1]) + 1.

那么综上所述，状态转移方程为：

细节问题：

初始化：我们需要手动初始化 i == n-1和j == 0的位置，dp[n-1][n-1] = dp[0][0] = 0,其他的位置为了不影响求min，我么可以初始化为最大值。不过由于我们会在填表过程中，对i == j的时候进行特殊处理，所以我们并不需要额外初始化。

在填表过程中，i == j - 1的时候，dp[i+1][j-1] 可能非法，当 s[i] = s[j] 的时候，dp[i][j] 需要填 0,而当s[i]!=s[j]的时候，dp[i][j] 需要填1，我们需要特殊处理。

填表顺序：从下往上填写每一行，每一行从左往右填写

返回值：dp[0][n-1]

代码如下：

class Solution {
public:int minInsertions(string s) {int n = s.size();vector<vector<int>> dp(n,vector<int>(n,0x3fffffff));// dp[0][0] = dp[n-1][n-1] = 0;for(int i = n - 1 ; i >= 0 ; --i){for(int j = i ; j < n ; ++j){if(i == j){dp[i][j] = 0 ; continue;} if(i == j - 1){dp[i][j] = s[i] == s[j] ? 0 : 1;continue;}if(s[i] == s[j]) dp[i][j] = dp[i+1][j-1];else dp[i][j] = min(dp[i+1][j] , dp[i][j-1]) + 1;}}return dp[0][n-1];}
};