1312.让字符串成为回文串的最少插入次数 详解！！看不懂你找我！！！！_s是一个字符串,仅包含字母a,b,c; 你可以做如下操作,在s任意位置插入一个字符 返回

题目描述

给你一个字符串 s ，每一次操作你都可以在字符串的任意位置插入任意字符。

请你返回让 s 成为回文串的 最少操作次数 。

输入：s = "mbadm"
输出：2
解释：字符串可变为 "mbdadbm" 或者 "mdbabdm" 。

 int minInsertions(string s) {
   
 }
1
2
3
4
5
6
7

题目解析

题目只给定一个参数，字符串s，需要将s 变成回文串，回想起判断字符串回文的时候经常使用[L…R] 范围上的尝试，因此此题先按照老套路定义范围上的动态规划尝试。
即 dp[i][j] 表示 字符串s[i…j]这段子串变成回文串所需要插入的最少次数

尝试解题

回文串的动态规划表是正方形的上半部分，要求L<=R，同时base case 是 对角线以及次对角线。

按照定义：
对角线dp[i][i] 代表 字符串 s[i…i] 变成回文串所需要插入的最少次数，毫无疑问，只有一个字符，所以主对角线全为0

再看次对角线，dp[i][i+1] 代表字符串s[i…i+1] 变成回文串所需要的最少插入次数，两个字符，只需判断s[i] 是否等于 s[i+1]，若二者相等，则为0， 不等则为1

好，接下来我们来看普遍位置怎么分析：

我们要判断 s[i…j] 变成回文串的最少插入次数：

1. 如果s[i] == s[j] 那么此时要求的就是 s[i+1…j-1] 变成回文串的最少插入次数了，即 dp[i+1][j-1]
2. 如果s[i] != s[j] 此时我们可以考虑 在 最右边插入一个 s[i] 那么就变成了 s[i+1…j] 的 最少插入次数 再 加上一次， 或者在最左边插入一个s[j] ，即 s[i…j-1] 的 最少插入次数 + 1
   此时的dp[i][j] = min(dp[i+1][j],dp[i][j-1]) +1

代码

 int minI