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

/*
 * @lc app=leetcode.cn id=1312 lang=cpp
 *
 * [1312] 让字符串成为回文串的最少插入次数
 *
 * https://leetcode-cn.com/problems/minimum-insertion-steps-to-make-a-string-palindrome/description/
 *
 * algorithms
 * Hard (64.47%)
 * Likes:    93
 * Dislikes: 0
 * Total Accepted:    7.5K
 * Total Submissions: 11.6K
 * Testcase Example:  '"zzazz"'
 *
 * 给你一个字符串 s ，每一次操作你都可以在字符串的任意位置插入任意字符。
 * 
 * 请你返回让 s 成为回文串的 最少操作次数 。
 * 
 * 「回文串」是正读和反读都相同的字符串。
 * 
 * 
 * 
 * 示例 1：
 * 
 * 
 * 输入：s = "zzazz"
 * 输出：0
 * 解释：字符串 "zzazz" 已经是回文串了，所以不需要做任何插入操作。
 * 
 * 
 * 示例 2：
 * 
 * 
 * 输入：s = "mbadm"
 * 输出：2
 * 解释：字符串可变为 "mbdadbm" 或者 "mdbabdm" 。
 * 
 * 
 * 示例 3：
 * 
 * 
 * 输入：s = "leetcode"
 * 输出：5
 * 解释：插入 5 个字符后字符串变为 "leetcodocteel" 。
 * 
 * 
 * 示例 4：
 * 
 * 
 * 输入：s = "g"
 * 输出：0
 * 
 * 
 * 示例 5：
 * 
 * 
 * 输入：s = "no"
 * 输出：1
 * 
 * 
 * 
 * 
 * 提示：
 * 
 * 
 * 1 <= s.length <= 500
 * s 中所有字符都是小写字母。
 * 
 * 
 */

 思路：labuladong回文问题终极篇：最小代价构造回文串

我们定义一个二维的dp数组，dp[i][j]的定义如下：对字符串s[i..j]，最少需要进行dp[i][j]次插入才能变成回文串。

我们想求整个s的最少插入次数，根据这个定义，也就是想求dp[0][n-1]的大小（n为s的长度）。

同时，base case 也很容易想到，当i == j时dp[i][j] = 0，因为当i == j时s[i..j]就是一个字符，本身就是回文串，所以不需要进行任何插入操作。

如果我们现在想计算dp[i][j]的值，而且假设我们已经计算出了子问题dp[i+1][j-1]的值了，那么也就可以认为s[i+1..j-1]已经是一个回文串了，所以通过dp[i+1][j-1]推导dp[i][j]的关键就在于s[i]和s[j]这两个字符。

如果s[i] == s[j]的话，我们不需要进行任何插入，只要知道如何把s[i+1..j-1]变成回文串即可

翻译成代码就是这样：

if (s[i] == s[j]) {
    dp[i][j] = dp[i + 1][j - 1];
}

当s[i] != s[j]时，无脑插入两次肯定是可以让s[i..j]变成回文串，但是不一定是插入次数最少的，最优的插入方案应该被拆解成如下流程：

步骤一，做选择，先将s[i..j-1]或者s[i+1..j]变成回文串。怎么做选择呢？谁变成回文串的插入次数少，就选谁呗。

步骤二，根据步骤一的选择，将s[i..j]变成回文。

如果你在步骤一中选择把s[i+1..j]变成回文串，那么在s[i+1..j]右边插入一个字符s[i]一定可以将s[i..j]变成回文；同理，如果在步骤一中选择把s[i..j-1]变成回文串，在s[i..j-1]左边插入一个字符s[j]一定可以将s[i..j]变成回文。

那么根据刚才对dp数组的定义以及以上的分析，s[i] != s[j]时的代码逻辑如下：

if (s[i] != s[j]) {
    // 步骤一选择代价较小的
    // 步骤二必然要进行一次插入
    dp[i][j] = min(dp[i + 1][j], dp[i][j - 1]) + 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;
}

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