【LeetCode】动态规划—1312. 让字符串成为回文串的最少插入次数（附完整Python/C++代码）

动态规划—1312. 让字符串成为回文串的最少插入次数

• 题目描述
• 前言
• 基本思路
  • 1. 问题定义
  • • 目标：
    • 举例：
  • 2. 理解问题和递推关系
  • • 动态规划思路：
  • 3. 解决方法
  • • 动态规划方法
    • 伪代码：
  • 4. 进一步优化
  • 5. 小总结
• Python代码
• • • Python代码解释：
• C++代码
• • • C++代码解释：
• 总结

题目描述

在这里插入图片描述

前言

最少插入次数使字符串变为回文 是一个经典的动态规划问题。我们需要计算出通过最少的插入次数将给定的字符串转换为回文字符串。回文字符串是指正读和反读相同的字符串。通过动态规划的思想，我们可以高效地解决这一问题，分析每个字符与其对称位置之间的关系。

基本思路

1. 问题定义

给定一个字符串 s，要求找到最少的插入步骤，使得这个字符串变为回文。

目标：

• 找到可以将字符串 s 转换为回文所需的最小插入次数。

举例：

• 输入："mbadm"
• 输出：2，因为通过插入字符可以将其变为 "mbdadbm" 或 "madbam"。

2. 理解问题和递推关系

如果我们要求插入最少次数，使得一个字符串变为回文，可以反过来思考：我们可以找到该字符串的 最长回文子序列，然后剩下的字符可以通过插入来补齐，从而形成一个回文。

动态规划思路：

1. 定义状态： 定义一个二维数组 dp[i][j]，表示在区间 s[i...j] 内，将该子串变为回文所需的最少插入次数。
2. 状态转移方程：
   • 当 s[i] == s[j] 时，不需要插入，dp[i][j] = dp[i+1][j-1]。
   • 当 s[i] != s[j] 时，我们可以选择插入字符使它们相等，因此有两种情况：
     1. 在 s[i] 前插入 s[j]，则状态转移为 dp[i][j] = dp[i][j-1] + 1；
     2. 在 s[j] 后插入 s[i]，则状态转移为 dp[i][j] = dp[i+1][j] + 1。
   • 最终取两者的最小值：

   dp[i][j] = \min(dp[i+1][j], dp[i][j-1]) + 1

3. 边界条件：
   • 当 i == j，即字符串长度为1时，已经是回文，不需要插入，因此 dp[i][i] = 0。
   • 当 i > j，这种情况不可能存在，值为 0。

3. 解决方法

动态规划方法

1. 初始化二维数组 dp，dp[i][j] 记录了从 i 到 j 的子串所需的最少插入次数。
2. 使用 状态转移方程 填充 dp 数组。
3. 最终结果保存在 dp[0][n-1] 中，n 是字符串的长度。

伪代码：

initialize dp array with size n x n
for length from 2 to n:
    for i from 0 to n-length:
        j = i + length - 1
        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]

4. 进一步优化

• 空间优化：可以使用一维数组优化空间复杂度，只记录相邻状态的值。

5. 小总结

• 问题转化：该问题可以通过寻找 最长回文子序列 的反向思路求解。
• 时间复杂度：该解法的时间复杂度为 O(n^2)，空间复杂度为 O(n^2)。

以上就是让字符串成为回文串的最少插入次数问题的基本思路。

Python代码

class Solution:
    def minInsertions(self, s: str) -> int:
        n = len(s)
        # 初始化dp数组，dp[i][j] 表示将s[i:j+1]变为回文所需的最少插入次数
        dp = [[0] * n for _ in range(n)]
        
        # 从长度为2开始遍历子串
        for length in range(2, n + 1):
            for i in range(n - length + 1):
                j = i + length - 1
                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]

Python代码解释：

1. 初始化：创建二维 dp 数组，dp[i][j] 表示将 s[i:j+1] 变为回文的最少插入次数。
2. 状态转移：通过比较 s[i] 和 s[j]，根据状态转移方程更新 dp 数组。
3. 返回结果：dp[0][n-1] 即为整个字符串变为回文的最少插入次数。

C++代码

class Solution {
public:
    int minInsertions(string s) {
        int n = s.size();
        // 初始化dp数组，dp[i][j] 表示将s[i:j+1]变为回文所需的最少插入次数
        vector<vector<int>> dp(n, vector<int>(n, 0));
        
        // 从长度为2开始遍历子串
        for (int length = 2; length <= n; ++length) {
            for (int i = 0; i <= n - length; ++i) {
                int j = i + length - 1;
                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];
    }
};

C++代码解释：

1. 初始化：创建二维数组 dp，dp[i][j] 表示将 s[i:j+1] 变为回文的最少插入次数。
2. 状态转移：通过动态规划递推公式更新 dp 数组。
3. 返回结果：dp[0][n-1] 即为将整个字符串变为回文的最少插入次数。

总结

• 核心思想：通过动态规划求解最少插入次数来将字符串转换为回文。该问题可以转化为找出 最长回文子序列，然后剩余的字符通过插入进行补齐。
• 时间复杂度：该方法的时间复杂度为 O(n^2)，适合处理中等规模的字符串问题。
• 应用场景：该问题展示了如何通过动态规划优化复杂问题的思路，同时也能帮助我们理解如何在字符串操作中利用递归关系处理类似的转换问题。