【动态规划】回文子串专题_动态规划 回文子串
赞
踩
文章目录
1. 【LeetCode】647. 回文子串
1.1 思路讲解
1.1.1 方法选择
这道题我们采用动态规划的解法，倒不是动态规划的解法对于这道题有多好，它并不是最优解。但是，这道题的动态规划思想是非常有用的，我们使用这道题的动态规划思想，可以让一些hard题变为easy题。
也就是说，这道题的动态规划思想其实就是起到了一个抛砖引玉的作用。
1.1.2 dp表的创建
如何表示出所有的子串的情况？可以用 i 表示某个子串的起始位置，用 j 来表示某个子串的末尾位置，暴力枚举，可以在N^2的时间复杂度内求出所有子串是否为回文子串。
所以，我们用二维dp[i][j]表来表示，以 i 位置为起始位置且以 j 位置为结尾的子串是否为回文子串。如果为回文子串那么dp[i][j]为true，否则为false。（我们人为规定 i <= j）
1.1.3 状态转移方程
我们要知道dp[i][j]为是否为回文子串，首先要判断 s[i] 是否等于 s[j]。
如果 s[i] != s[j]，那么不管 i 和 j 中间的元素序列是怎样的，以 i 位置为起始位置，以 j 位置为终止位置的子串一定不为回文子串。
如果 s[i] == s[j]，那么需要对 i 和 j 的位置进行判断。
- 如果 i == j，那么说明当前初识位置和末尾位置在同一个位置，也就是说，子串只有一个元素，此时根据题意它为回文子串；
- 如果 i + 1 == j，那么 i 和 j 的位置是相邻的，此时它们中间没有元素，它们位置上的元素又相同，那么一定是回文子串；
- 如果 i + 1 < j，说明 i 位置 和 j 位置中间还有其他元素，此时只需判断dp[i+1][j-1]为true还是false即可。
1.1.4 填表顺序
由于我们求dp[i][j]的时候，需要用到 dp[i+1][j-1]，且 i 的循环为外层的循环，所以让 i 从大到小循环即可。
1.2 整体代码
class Solution { public: int countSubstrings(string s) { int n = s.size(); // 创建二维dp表，dp表中每个位置的初始值为false vector<vector<bool>> dp(n, vector<bool>(n)); int ret = 0; // 用于保存有多少位true的dp位置，即有多少个回文子串 // 在循环时 i 从大到小进行循环 for (int i = n - 1; i >= 0; --i) { // j的循环顺序其实无所谓，只要循环的区间在[i, n)即可 for (int j = i; j < n; ++j) { // 根据状态转移方程求dp[i][j] if (s[i] == s[j]) dp[i][j] = i + 1 < j ? dp[i+1][j-1] : true; // 如果dp[i][j]为true，增加ret if (dp[i][j]) ++ret; } } return ret; } };
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
2. 【LeetCode】5. 最长回文串
2.1 思路讲解
与求回文子串思路差别不大
它也就是求出每一个回文子串后，不是统计有多少个回文子串，而是挑出最长的那个回文子串并在循环结束之后返回即可。
代码也只不过改动了一点点而已。
2.2 代码实现
class Solution { public: string longestPalindrome(string s) { int n = s.size(); vector<vector<bool>> dp(n, vector<bool>(n)); int start = 0; // 最长的回文子串的起始位置 int len = 0; // 最长的回文子串的长度 for (int i = n - 1; i >= 0; --i) { for (int j = i; j < n; ++j) { if (s[i] == s[j]) dp[i][j] = i + 1 < j ? dp[i+1][j-1] : true; // 如果该位置为回文子串，那么判断长度是否大于之前最长的长度 // 如果大于，则对起始位置和最长长度进行更新 if (dp[i][j] == true && j - i + 1 > len) { len = j - i + 1; start = i; } } } // 根据起始位置和长度返回最长回文子串 return s.substr(start, len); } };
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
3.【LeetCode】094. 分割回文串II
3.1 解题思路
3.1.1 创建dp表
这道题我们使用动态规划的方法来解，首先创建一个大小为字符串长度的dp表。dp[i] 表示 s[0, i] 的字符串最小划分多少次可以全划分为回文串。
3.1.2 状态转移方程
求状态转移方程，我们要考虑两种情况。s[0, i] 的字符串是回文串和不是回文串的情况。
注意，这里假设我们已经知道了哪段字符串是不是回文串，至于是如何知道的后面会说。
- 如果s[0, i]是回文串，那么问题很简单，不用切割就行，即dp[i] = 0;
- 如果s[0, i]不是回文串，我们要新增一个变量 j ，j 的范围为 (0, i]，这里说明一些j的边界情况，j 要大于0的原因是 j 为0的情况即不用分割s[0, i]的情况（即s[0, i]为回文串的情况），j 为 i 的情况即 s[0, i-1] 中找不到从0开始且为回文串的情况。用这个 j 变量，我们遍历 j 的情况，j 是小于等于 i 的，那么 dp[j-1] 的值我们是知道的。如果从 j 到 i 的字符串是回文串，那么我们就令 dp[i] = min(dp[i], dp[j - 1] + 1); 遍历所有 j 的情况，就能求出 dp[i] 的最小值了。
3.1.3 提前求出所有子串是否是回文串
这个通过上面的题解也就能知道了。
3.2 整体代码
class Solution { public: int minCut(string s) { int n = s.size(); // 求出所有子串是否为回文串 vector<vector<bool>> isPal(n, vector<bool>(n)); for (int i = n - 1; i >= 0; --i) for (int j = i; j < n; ++j) if (s[i] == s[j]) isPal[i][j] = i + 1 < j ? isPal[i+1][j-1] : true; // 创建dp表，由于是求最小值，可以先将所有位置初始化为最大 vector<int> dp(n, INT_MAX); for (int i = 0; i < n; ++i) { if (isPal[0][i]) dp[i] = 0; else { for (int j = 1; j <= i; ++j) if (isPal[j][i]) dp[i] = min(dp[i], dp[j-1] + 1); } } return dp[n-1]; } };
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
4.【LeetCode】516. 最长回文子序列
4.1 思路讲解
4.1.1 创建dp表
此题采用动态规划的方法，创建一个二维dp表，dp[i][j]表示s[i, j]中最大回文子序列的长度。且我们人为规定 i 是一定小于等于 j 的。
4.1.2 状态转移方程
在求dp[i][j]时，首先要判断s[i]和s[j]是否相同。
如果 s[i] == s[j]
- 如果 i == j，说明 i 与 j 的位置相同，此时dp[i][j] 就为 1
- 如果 i + 1 == j，说明 i 与 j 相邻，此时dp[i][j] 就为2
- 其他情况下，说明 i 和 j 中间有其他元素，那么此时dp[i][j] = dp[i+1][j-1] + 2；
如果s[i] != s[j]
那么此时，说明不能同时以 i 为开头和以 j 为结尾，我们去掉这种情况寻找一个最大子序列即可。方法就是在 dp[i+1, j] 和 dp[i, j-1] 中选一个最大的即可。即dp[i][j] = max(dp[i+1[j], dp[i][j-1]);
4.1.3 不需考虑边界问题
在求dp[i][j]的时候，我们可能会用到 i + 1 和 j - 1，在它们有可能越界的时候，一定是 i 等于 j 的时候。我们创建的dp表是二维的，我们可以想到，在可能越界的时候，就是左上角的位置或者右下角的位置，但其实这两个位置满足 i == j，那么dp[i][j] 就会被直接赋值为1，此时就不会用到 i + 1 和 j - 1 了，所以其实我们不用考虑越界的情况。
4.2 整体代码
class Solution { public: int longestPalindromeSubseq(string s) { int n = s.size(); // 创建二维dp表，dp[i][j]表示s[i, j]最大子序列的长度 vector<vector<int>> dp(n, vector<int>(n)); // dp[i][j]需要用到dp[i+1][j-1] // 所以i从大到小循环，j从小到大循环，且i是小于等于j的 for (int j = 0; j < n; ++j) { for (int i = j; i >= 0; --i) { 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; } else dp[i][j] = max(dp[i+1][j], dp[i][j-1]); } } return dp[0][n-1]; } };
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
5. 【LeetCode】1312. 让字符串成为回文串的最少插入次数
5.1 思路讲解
5.1.1 创建dp表
采用动态规划的解法，可以借鉴以上题的思路。创建二维dp表，dp[i][j]表示 i 到 j 位置变成回文串的最小操作次数。（我们人为规定 i 是小于等于 j 的）
5.1.2 状态转移方程
同样我们要分 s[i] == s[j] 和 s[i] != s[j] 的情况讨论。
如果 s[i] == s[j]
- 如果 i == j，那么此时 i 与 j 的位置相同，一个字符本身就是回文串，dp[i][j] = 0
- 如果 i + 1 == j，那么此时 i 与 j 位置相同，此时这两个字符同样也是回文串，dp[i][j] = 0
- 如果 i + 1 < j ，那么此时 i 与 j 中间有其他字符，dp[i+1][j-1]为 i 和 j 中间字符串要变为回文串的最小操作次数，因为 s[i] == s[j]，所以此时加上 i 和 j 位置的字符之后， dp[i][j] = dp[i+1][j-1]。
如果 s[i] != s[j]
i 和 j 位置的字符不相同，那么此时只需找到 dp[i+1][j] 和 dp[i][j-1] 的最小值，然后将最小的那个加1即可，即dp[i][j] = min(dp[i+1][j], dp[i][j-1]) + 1; 就相当于再在另一端补上一个与 s[i] 或者 s[j] 相同的字符即可。
5.1.3 不需考虑边界问题
这道题和第四题一样，都是需要考虑越界的，具体原因和第四题相同。
在求dp[i][j]的时候，我们可能会用到 i + 1 和 j - 1，在它们有可能越界的时候，一定是 i 等于 j 的时候。我们创建的dp表是二维的，我们可以想到，在可能越界的时候，就是左上角的位置或者右下角的位置，但其实这两个位置满足 i == j，那么dp[i][j] 就会被直接赋值为0，此时就不会用到 i + 1 和 j - 1 了，所以其实我们不用考虑越界的情况。
5.2 整体代码
class Solution { public: int minInsertions(string s) { int n = s.size(); // dp[i][j]表示s[i, j]变成回文串的最小操作次数 vector<vector<int>> dp(n, vector<int>(n, INT_MAX)); // dp[i][j] 需要用到 dp[i+1][j-1] // 所以i应该从大到小遍历，j应该从小到大遍历 // 且i是要小于等于j的，所以i的初始值为j // 因为i的初始值为j，所以j在循环外层，i在内层 for (int j = 0; j < n; ++j) { for (int i = j; i >= 0; --i) { if (s[i] == s[j]) dp[i][j] = i + 1 < j ? dp[i+1][j-1] : 0; else dp[i][j] = min(dp[i][j-1], dp[i+1][j]) + 1; } } return dp[0][n-1]; } };
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
