动态规划-回文串系列——1312.让字符串变成回文串的最小插入次数

1.题目解析

题目来源：1312.让字符串变成回文串的最小插入次数——力扣

测试用例

2.算法原理

1.状态表示

一维dp表无法存储任意区间内将字符串变为回文子串的最小插入次数，所以使用二维dp表存储将[i,j]区间的字符串变为回文子串的最小插入次数

dp[i][j]:将[i,j]区间的字符串变为回文子串的最小插入次数

2.状态转移方程

这里首先判断两端字符是否相同，如果相同则需要判断[i,j]区间字符个数，然后向中间移动取dp表的值，反之不相同则需要对左插与右插两种情况取min值

3.初始化

dp表只有中间对角线与中间对角线的右上方对角线两条路线可能会用到下三角的值，但是下三角全为0不影响填表，因此不用初始化

4.填表顺序

填写时可能用到左下角或者左边与正下方的值，所以填表需要从下至上且每行从左到右

5.返回值 

根据状态表示可以直接返回dp[0][n-1]

3.实战代码

代码解析

class Solution {
public:
    int minInsertions(string s) {
        int n = s.size();
        vector<vector<int>> dp(n, vector<int>(n));

        for (int i = n - 1; i >= 0; i--) {
            for (int j = i + 1; j < n; j++) {
                if (s[i] == s[j]) {
                    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];
    }
};