本文探讨了如何使用动态规划解决LeetCode中的两道回文串问题——最小代价构造回文串和分割回文串。通过思路分析和代码实现，详细解释了如何利用状态压缩技巧来优化算法，降低复杂度。
目录
前言
动态规划的通用套路和状态压缩技巧具有很强的通用性
LeetCode1312之最小代价构造回文串
给你一个字符串 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
思路分析
我们定义一个二维的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]就是一个字符，本身就是回文串，所以不需要进行任何插入操作。
假设为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]变成回文串即可：
如果s[i] != s[j]的话，就比较麻烦了，比如下面这种情况
最简单的想法就是，先把s[j]插到s[i]右边，同时把s[i]插到s[j]右边，这样构造出来的字符串一定是回文串：
但是，这是不是就意味着代码可以直接这样写呢？
if (s[i] != s[j]) {
// 把 s[j] 插到 s[i] 右边，把 s[i] 插到 s[j] 右边
dp[i][j] = dp[i + 1][j - 1] + 2;
}
不对，比如说如下这两种情况，只需要插入一个字符即可使得s[i..
最低0.47元/天 解锁文章
扫一扫
1029
被折叠的 条评论
为什么被折叠?
到【灌水乐园】发言
