【动态规划篇】：当回文串遇上动态规划--如何用二维DP“折叠”字符串？

✨感谢您阅读本篇文章，文章内容是个人学习笔记的整理，如果哪里有误的话还请您指正噢✨
✨ 个人主页：余辉zmh–CSDN博客
✨ 文章所属专栏：动态规划篇–CSDN博客

一.回文串类DP

核心思想（判断所有子串是否是回文子串）

1.状态表示：

定义二维数组dp[i][j]，表示字符串s区间[i,j]的子串是否是回文串，其中i位置的字符是子串的起始位置，j位置的字符是子串的结束位置，存储每一个子串的信息，是dp[i][j]为true，不是为false。

2.状态转移方程：

• 如果两端的字符s[i]==s[j]，分为三种情况：
  • 如果子串长度为1，则下标i==j，说明字串是一个单独的字符，则一定是回文子串，dp[i][j]=true。
  • 如果子串长度为2，则下标i+1=j，说明子串是两个相邻的字符，并且前提条件两个字符相同，所以也一定是回文子串，dp[i][j]=true。
  • 如果子串长度大于2，则下标j-i>2，需要检查内部区间[i+1,j-1]部分的子串是否是回文子串，如果是并且两端的字符也相等，所以区间[i,j]部分的字串也是回文子串，dp[i][j]=true；如果不是，那区间[i,j]部分的字串也就一定不是回文子串，dp[i][j]=false。
• 如果两端的字符s[i]!=s[j]，则区间[i,j]的子串一定不是回文子串，dp[i][j]=false。

3.初始化：

单个字符一定是回文子串，所以初始值可以设置为true。

4.填表顺序：

根据状态转移方程来决定，当前状态dp[i][j]需要用到前一个状态dp[i+1][j-1]，在二维数组中，位于[i,j]位置的左下角，所以填表时，需要从最后一行到第一行，其中每一行按照从左往右的顺序。

因为下标i<=j，所以二维数组中，只需填表斜对角线的上半部分即可。

5.返回值：

需要根据题意来决定。

注意：上面讲解的是关于如何判断所有子串是否是回文子串，并不是每一道的解决步骤都是这样，具体解决方式需要根据题意来决定，但所有的回文串类DP都是在此基础上变形，所以该思想对于解决回文串类DP非常重要。

二.例题

1.回文子串

题目：

算法原理：

题意要求统计所有的回文子串个数，所以可以用二维数组状态表dp[i][j]存储所有子串是否是回文子串的信息，是为true，不是为false。所以最后填完状态表后只需遍历一遍，统计true的个数即可。

代码实现：

int countSubstrings(string s){int n = s.size();//状态表示 dp[i][j]表示以i位置字符为开头，j位置字符为结尾的子串是否是回文子串//状态表中会存储每个子串是否是回文子串的信息vector<vector<bool>> dp(n, vector<bool>(n));int ret = 0;//填表顺序 从最后一行到第一行 因为当前状态值需要用到左下角的状态值for (int i = n - 1; i >= 0; i--){for (int j = i; j < n; j++){if(s[i]==s[j]){if (i == j || i + 1 == j || dp[i + 1][j - 1] == true){dp[i][j] = true;}}//如果当前子串是回文子串，个数加一if (dp[i][j] == true){ret += 1;}}}//返回值return ret;
}

2.最长回文子串

题目：

算法原理：

题意要求找到最长回文子串并返回，所以在次之前依然需要找到所有的回文子串才能找到最长长度的那个，还是用二维数组状态表dp[i][j]存储所有子串的信息，在填表的时候，如果当前区间的子串是回文子串，就判断是否更新最长长度，注意还要保留最长回文子串的起始位置。

代码实现：

string longestPalindrome(string s){int n = s.size();//状态表示 dp[i][j]表示以i位置字符为开头，j位置字符为结尾的子串是否是回文子串//状态表中会存储每个子串是否是回文子串的信息vector<vector<int>> dp(n, vector<int>(n));int maxlen = 0;int begin = 0;//填表for (int i = n - 1; i >= 0; i--){for (int j = i; j < n; j++){if(s[i]==s[j]){if (i == j || i + 1 == j || dp[i + 1][j - 1] == true){dp[i][j] = true;}}if (dp[i][j] == true){//更新最长的长度和开头下标maxlen = max(maxlen, j - i + 1);if (maxlen == j - i + 1){begin = i;}}}}//返回值return s.substr(begin, maxlen);
}

3.分割回文串4

题目：

算法原理：

根据题意要求，需要将原字符串分割成三个回文字符串，所以依然需要知道所有的回文子串，还是用二维数组状态表dp[i][j]存储所有子串的信息。

假设原字符串分成三个区间的字符串，[0,i-1]，[i,j]，[j+1,n-1]区间，并且i>=1，j<=n-2（因为[0,i-1]区间和[j+1,n-1]区间的字符串至少长度为1），如果存在[i,j]区间的字符串是回文串，并且[0,i-1]区间和[j+1,n-1]的字符串也是回文串，就能分成三个，反之则不存在。

代码实现：

bool checkPartitioning(string s){int n = s.size();//状态表示vector<vector<bool>> dp(n, vector<bool>(n));//填表for (int i = n - 1; i >= 0; i--){for (int j = i; j < n; j++){if (s[i] == s[j]){if (i == j || i + 1 == j || dp[i + 1][j - 1] == true){dp[i][j] = true;}}}}//返回值 分割成三个回文子串 [0,i-1],[i,j],[j+1,n-1]for (int i = 1; i < n - 1; i++){for (int j = i; j < n - 1; j++){if (dp[0][i - 1] == true && dp[i][j] == true && dp[j + 1][n - 1] == true){return true;}}}return false;
}

4.分割回文串2

题目：

算法原理：

根据题意还是需要先知道所有子串是否是回文子串，所以先预处理状态表dp[i][j]，找到所有区间的回文子串。

定义一个一维数组min_cut[i]状态表，

状态表示：[0,i]区间内的字符串，分割成回文子串最小的分割次数。

状态转移方程：分为两种情况，

如果[0,i]区间内的字符串已经是回文子串，最小分割次数就为0，min_cut[i]=0；

如果[0,i]区间内的字符串不是回文子串，用下标j遍历区间[0,i]，如果区间[j,i]字符串是回文子串，判断区间[0,j-1]的字符串分割成回文子串的最小分割次数，也就是找到min_cut[j-1]的最小值然后加一。

最后返回值就是区间[0,n-1]的字符串分割成回文子串的最小分割数，也就是min_cut[n-1]。

代码实现：

int minCut(string s){int n = s.size();//先获取每个子串是否是回文子串的信息,存放到二维状态表中vector<vector<bool>> dp(n, vector<bool>(n));for (int i = n - 1; i >= 0; i--){for (int j = i; j < n; j++){if (s[i] == s[j]){if (i == j || i + 1 == j || dp[i + 1][j - 1] == true){dp[i][j] = true;}}}}//状态表示 min_cut[i]表示[0,i]区间内的子串，分割成回文子串最小的分割次数//初始化 因为要去前状态中的最小值，所以状态表中全部先初始化为最大值vector<int> min_cut(n, INT_MAX);//填表for (int i = 0; i < n; i++){if (dp[0][i] == true){min_cut[i] = 0;}else{for (int j = i; j > 0; j--){if (dp[j][i] == true){//状态转移方程min_cut[i] = min(min_cut[j - 1] + 1, min_cut[i]);}}}}//返回值return min_cut[n - 1];
}

5.最长回文子序列

题目：

算法原理：

本道题有点不同，需要找到的是回文子序列，关键点：回文子序列是允许字符不连续的，因此需要灵活利用状态转移。

状态表示：二维数组dp[i][j]，表示s字符串[i,j]区间内，最长回文子序列的长度。

状态转移方程：分为两种情况，

如果两端的字符s[i]==s[j]：

如果下标i==j，说明单独的一个字符表示回文子序列，不存在区间[i+1,j-1]，长度直接为1。

如果下标i+1==j，说明两端的字符表示回文子序列，不存在区间[i+1,j-1]，长度直接为2。

如果下标j-i>2，可以将这两个字符加入回文子序列的两端，因此找到区间[i+1,j-1]内的最长回文子序列长度然后加2，dp[i][j]=dp[i+1][j-1]+2。

如果两度的字符s[i]!=s[j]：

无法同时包含这两个字符，需要舍弃左端或者右端的字符，然后找剩余区间中的最长回文子序列长度，dp[i][j]=max(dp[i+1][j],dp[i][j-1])。

填表顺序：计算当前状态dp[i][j]的值，需要先知道前三个状态的值，dp[i+1][j-1],dp[i+1][j],dp[i][j-1]，在二维数组中分别位于当前位置的左下角，左侧和下侧。因此填表时需要从最后一行到第一行，其中每一行从左往右。

代码实现：

int longestPalindromeSubseq(string s){int n = s.size();//状态表示 dp[i][j]表示[i,j]区间内，最长回文子序列的长度vector<vector<int>> dp(n, vector<int>(n));//填表 从上往下，其中每一行从左往右for (int i = n - 1; i >= 0; i--){for (int j = i; j < n; j++){//如果当前两个位置的字符相等，找区间内的最长回文子序列的长度if (s[i] == s[j]){if (i == j){dp[i][j] = 1;}else if (i + 1 == j){dp[i][j] = 2;}else{dp[i][j] = dp[i + 1][j - 1] + 2;}}//如果当前两个位置的字符不相等，找[i+1,j]和[i,j-1]两个区间内的最长回文子序列的长度else{dp[i][j] = max(dp[i][j - 1], dp[i + 1][j]);}}}//返回值return dp[0][n - 1];
}

6.让字符串成为回文串的最少插入次数

题目：

算法原理：

状态表示：二维数组dp[i][j]，表示s字符串[i,j]区间内字符串成为回文串的最少插入次数

状态转移方程：分为两种情况，

如果两端的字符s[i]==s[j]：

如果下标i==j，说明单独的一个字符表示长度为1的回文串，不用再插入字符，次数直接为0。

如果下标i+1==j，说明两端的字符表示长度为2的回文串，不用再插入字符，长次数还是为0。

如果下标j-i>2，可以将这两个字符直接加入回文串的两端，因此找到区间[i+1,j-1]内的回文子串最少插入次数，dp[i][j]=dp[i+1][j-1]。

如果两度的字符s[i]!=s[j]：

无法同时包含这两个字符，需要舍弃左端的字符然后在左侧插入一个右端的字符或者舍弃右端的字符然后在右侧插入一个左端的字符，然后找剩余区间中的回文子串最少插入次数，dp[i][j]=max(dp[i+1][j]+1,dp[i][j-1]+1)。

填表顺序：计算当前状态dp[i][j]的值，需要先知道前三个状态的值，dp[i+1][j-1],dp[i+1][j],dp[i][j-1]，在二维数组中分别位于当前位置的左下角，左侧和下侧。因此填表时需要从最后一行到第一行，其中每一行从左往右。

代码实现：

int minInsertions(string s){int n = s.size();//状态表示 dp[i][j]表示[i,j]区间内字符串成为回文串的最少插入次数vector<vector<int>> dp(n, vector<int>(n));//填表 从最后一行到第一行，其中每一行从左往右for (int i = n - 1; i >= 0; i--){for (int j = i; j < n; j++){if (s[i] == s[j]){if (i == j || i + 1 == j){dp[i][j] = 0;}else{dp[i][j] = dp[i + 1][j - 1];}}else{dp[i][j] = min(dp[i][j - 1] + 1, dp[i + 1][j] + 1);}}}//返回值return dp[0][n - 1];
}

以上就是关于回文串类DP例题的讲解，如果哪里有错的话，可以在评论区指正，也欢迎大家一起讨论学习，如果对你的学习有帮助的话，点点赞关注支持一下吧！！！