【动态规划】回文串问题

题目描述：

思路讲解：
本道题需要我们判断字符串中所有可能的子串是否为回文，并统计总数，回文子串是正着读与倒着读一致的连续子串，我们可以通过过二维状态数组记录子串是否为回文，进而统计所有回文子串的数目。以下是具体思路：

1. 状态表示：dp[i][j] 表示字符串中从索引 i 到 j（i <= j）的子串 s[i…j] 是否为回文子串（true 表示是，false 表示否）
2. 状态转移方程：
   • 核心条件：s[i] == s[j]（子串首尾字符必须相同）
   • 辅助条件（满足其一即可）：
     • 若 i == j（子串长度为 1，单个字符本身是回文）
     • 若 i + 1 == j（子串长度为 2，两个相同字符构成回文）
     • 若 i + 1 < j（子串长度>=3），则需内部子串 s[i+1…j-1] 是回文（即 dp[i+1][j-1] == true）
3. 初始化
   • 初始时 dp 数组全为 false，通过后续遍历更新状态
4. 填写 DP 表与结果保存：
   • 按照从下到上、从右到左的计算顺序：外层循环从字符串末尾索引 i = n-1 遍历到 0，内层循环从 i 遍历到 n-1（确保 i <= j），这种顺序保证计算 dp[i][j] 时，内部子串 dp[i+1][j-1] 已被计算
   • 维护变量 ret，每当 dp[i][j] 被判定为 true（即子串 s[i…j] 是回文）时，ret 加 1
5. 结果返回：遍历结束后，ret 即为所有回文子串的总数

编写代码：

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

题目描述：

思路讲解：
本道题需要我们判断所有可能子串是否为回文，并记录最长的那个，回文子串是正着读与倒着读一致的连续子串，我们可以通过过二维状态数组记录子串是否为回文，同时记录最长回文子串的长度和起始位置，进而获得最长回文子串。以下是具体思路：

1. 状态表示：dp[i][j] 表示子串 s[i…j]（i <= j）是否为回文子串（true 表示是，false 表示否）
2. 状态转移方程：
   • 核心条件：s[i] == s[j]（首尾字符必须相同）
   • 辅助条件（满足其一）：
     • i == j（长度为 1 的子串，单个字符必为回文）
     • i + 1 == j（长度为 2 的子串，两相同字符构成回文）
     • i + 1 < j（长度>=3），则内部子串 s[i+1…j-1] 必须为回文（即 dp[i+1][j-1] == true）
3. 初始化：
   • dp 数组初始全为 false，通过遍历更新
4. 填写 DP 表：
   • 按照从下到上、从左到右的计算顺序：外层循环从字符串末尾索引 i = n-1 遍历到 0，内层循环从 i 遍历到 n-1（确保 i <= j），这种顺序保证计算 dp[i][j] 时，内部子串 dp[i+1][j-1] 已被计算
5. 最长回文子串追踪：
   • 用 pos 记录最长回文子串的起始索引，len 记录其长度（初始为 1，默认单个字符）
   • 每当 dp[i][j] 为 true 时，计算子串长度 j - i + 1，若大于当前 len，则更新 pos = i 和 len = j - i + 1
6. 结果返回：
   • 遍历结束后，通过 s.substr(pos, len) 截取并返回最长回文子串

编写代码：

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

题目描述：

思路讲解：

本道题需要我们判断字符串能否分割为 3 个非空回文子串，关键是先高效判断任意子串是否为回文，再枚举分割点验证条件。以下是具体思路：

1. 状态表示：dp[i][j] 表示子串 s[i…j]（i <= j）是否为回文子串（true 表示是，false 表示否）
2. 状态转移方程：
   • 核心条件：s[i] == s[j]（首尾字符必须相同）
   • 辅助条件（满足其一）：
     • i == j（长度为 1 的子串，单个字符必为回文）
     • i + 1 == j（长度为 2 的子串，两相同字符构成回文）
     • i + 1 < j（长度>=3），则内部子串 s[i+1…j-1] 必须为回文（即 dp[i+1][j-1] == true）
3. 初始化：
   • dp 数组初始全为 false，通过遍历更新
4. 填写 DP 表：
   • 按照从下到上、从左到右的计算顺序：外层循环从字符串末尾索引 i = n-1 遍历到 0，内层循环从 i 遍历到 n-1（确保 i <= j），这种顺序保证计算 dp[i][j] 时，内部子串 dp[i+1][j-1] 已被计算
5. 分割点枚举与验证：
   • 定义两个分割点 i 和 j（1 <= i <= j <= n-2），将字符串分为三部分：s[0…i-1]、s[i…j]、s[j+1…n-1]
   • 遍历所有可能的 i 和 j，若三部分子串对应的 dp[0][i-1]、dp[i][j]、dp[j+1][n-1] 均为 true，则返回 true
6. 结果返回：
   • 若遍历所有分割点均不满足条件，返回 false；否则返回 true

编写代码：

class Solution {
public:bool checkPartitioning(string s) {int n = s.size();vector<vector<bool>> dp(n,vector<bool>(n,false));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;}}}for(int i = 1 ; i < n - 1; i++){for(int j = i ; j < n - 1 ; j++){if(dp[0][i-1] && dp[i][j] && dp[j+1][n-1]){return true;}}}return false;}
};

题目描述：

思路讲解：
本道题需要我们计算将字符串分割成一些回文串的最少分割次数，我们可以先预处理回文子串判断，再计算最少分割次数。以下是具体思路：

1. 状态表示：
   • g[i][j] 表示子串 s[i…j]（i <= j）是否为回文子串（true 表示是）
   • f[i] 表示将子串 s[0…i] 分割为回文子串的最少分割次数
2. 回文判断的状态转移方程（g数组）：
   • 核心条件：s[i] == s[j]（首尾字符相同）
   • 辅助条件（满足其一）：
     • i == j（长度为 1 的子串，单个字符必为回文）
     • i + 1 == j（长度为 2 的子串，两相同字符构成回文）
     • i + 1 < j（长度>=3），则内部子串 s[i+1…j-1] 必须为回文（即 dp[i+1][j-1] == true）
3. 回文判断的填写 DP 表（g数组）：
   • 按照从下到上、从左到右的计算顺序：外层循环从字符串末尾索引 i = n-1 遍历到 0，内层循环从 i 遍历到 n-1（确保 i <= j），这种顺序保证计算 dp[i][j] 时，内部子串 dp[i+1][j-1] 已被计算
4. 最少分割次数的状态转移（f 数组）：
   • 若 g[0][i] == true（整个子串是回文），则 f[i] = 0（无需分割）
   • 否则，枚举分割点 j（1 <= j <= i）：若 g[j][i] == true（子串 s[j…i] 是回文），则 f[i] = min(f[i], f[j-1] + 1)（在 s[0…j-1] 的最少分割次数基础上 + 1）
5. 初始化：
   • f 数组初始化为 INT_MAX
6. 回文判断的填写 DP 表（f数组）：
   • 外层遍历 i 从 0 到 n-1，对每个 i 按上述规则更新 f[i]
7. 结果返回：
   • 最终结果为 f[n-1]（子串 s[0…n-1] 的最少分割次数）

编写代码：

class Solution {
public:int minCut(string s) {int n = s.size();vector<int> f(n,INT_MAX);vector<vector<bool>> g(n,vector<bool>(n,false));for(int i = n - 1 ; i >= 0 ; i--){for(int j = i ; j < n ; j++){if(s[i] == s[j])g[i][j] = i + 1 < j ? g[i+1][j-1] : true;}}for(int i = 0 ; i < n ; i++){if(g[0][i] == true){f[i] = 0;}else{for(int j = i ; j > 0 ; j--){if(g[j][i] == true){f[i] = min(f[i],f[j-1] + 1);}}}}return f[n-1];}
};

题目描述：

思路讲解：

本道题需要我们计算最长回文子序列的长度，我们可以通过二维状态数组记录子串中最长回文子序列的长度。以下是具体思路：

1. 状态表示：dp[i][j] 表示子串 s[i…j]（i <= j）中最长回文子序列的长度
2. 状态转移方程：
   • 若 s[i] != s[j]：最长回文子序列只能来自左侧子串或右侧子串，即 dp[i][j] = max(dp[i+1][j], dp[i][j-1])
   • 若 s[i] == s[j]：
     • 若 i + 1 < j（子串长度>=3），则 dp[i][j] = dp[i+1][j-1] + 2（中间子串的最长回文长度加 2，即两端字符）
     • 若 i == j（长度 1），则 dp[i][j] = 1（单个字符本身）
     • 若 i + 1 == j（长度 2），则 dp[i][j] = 2（两个相同字符）
3. 初始化：
   • 初始时 dp 数组全为 0，通过遍历更新
4. 填写 DP 表：
   • 按照从下到上，从左到右遍历：外层循环 i 从 n-1 到 0，内层循环 j 从 i 到 n-1，此顺序确保计算 dp[i][j] 时，dp[i+1][j]、dp[i][j-1] 和 dp[i+1][j-1] 已确定
5. 结果返回：
   • 整个字符串的最长回文子序列长度存储在 dp[0][n-1] 中，直接返回即可

编写代码：

class Solution {
public:int longestPalindromeSubseq(string s) {int n = s.size();vector<vector<int>> dp(n,vector<int>(n,0));for(int i = n - 1 ; i >= 0 ; i--){for(int j = i ; j < n ; j++){if(s[i] != s[j]) dp[i][j] = max(dp[i+1][j],dp[i][j-1]);else{dp[i][j] = i + 1 < j ? dp[i+1][j-1] + 2 : j - i + 1;}}}return dp[0][n-1];}
};

题目描述：

思路讲解：

本道题需要我们计算通过最少插入字符操作使字符串成为回文串，我们可以通过二维状态数组计算将子串转换为回文串所需的最少插入次数。以下是具体思路：

1. 状态表示：dp[i][j] 表示将子串 s[i…j]（i <= j）转换为回文串所需的最少插入次数
2. 状态转移方程：
   • 若 s[i] != s[j]：需通过插入字符使首尾对称，选择插入次数更少的方案：
     • dp[i][j] = min(dp[i+1][j], dp[i][j-1]) + 1
     • dp[i+1][j] 是忽略 s[i] 后子串的插入次数（需插入 s[i] 对称字符），dp[i][j-1] 是忽略 s[j] 后子串的插入次数（需插入 s[j] 对称字符），两者取最小值后加 1 次插入
   • 若 s[i] == s[j]：首尾已对称，插入次数取决于内部子串：
     • dp[i][j] = i + 1 < j ? dp[i+1][j-1] : 0
     • 若子串长度>=3（i+1 < j），则依赖内部子串 s[i+1…j-1] 的插入次数；若长度为 1（i == j）或 2（i+1= j），则无需插入（本身对称或已满足回文）
3. 初始化：
   • 初始时 dp 数组全为 0，通过遍历更新
4. 填写 DP 表：
   • 按照从下到上，从左到右的顺序：外层循环 i 从 n-1 到 0，内层循环 j 从 i 到 n-1，此顺序确保计算 dp[i][j] 时，dp[i+1][j]、dp[i][j-1] 和 dp[i+1][j-1] 已完成计算
5. 结果返回：
   • 整个字符串 s[0…n-1] 转换为回文串的最少插入次数存储在 dp[0][n-1] 中，直接返回即可

本道题还可以将问题进行转换：

• 字符串要成为回文串，需保证所有字符对称。而最长回文子序列是原字符串中 “天然对称” 的最大部分，无需额外插入字符即可维持对称结构。因此：原字符串中不属于最长回文子序列的字符，都需要通过插入对称字符来补全回文结构。
• 最少插入次数 = 字符串长度 - 最长回文子序列的长度

编写代码：

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