【算法日记】Day 10 动态规划专题——区间DP与回文串最少插入次数

1. 题目题目LeetCode 1312. 让字符串成为回文串的最少插入次数核心思路这道题是一个典型的区间 DP问题。设dp[l][r]表示将子串s[l...r]变成回文串所需要插入的最少字符数。若s[l] s[r]那么两端字符可以直接配对答案继承内部区间dp[l 1][r - 1]若s[l] ! s[r]则必须在左侧或右侧补一个字符使其中一边完成匹配因此状态转移为min(dp[l 1][r], dp[l][r - 1]) 1。复杂度时间复杂度为O(n^2)空间复杂度为O(n^2)。2. 代码class Solution { public: int minInsertions(string s) { int n s.size(); vectorvectorint dp(n, vectorint(n, 0)); for (int i 1; i n; i) { dp[i - 1][i] s[i - 1] s[i] ? 0 : 1; } for (int l n - 3; l 0; --l) { for (int r l 2; r n; r) { if (s[l] s[r]) dp[l][r] dp[l 1][r - 1]; else dp[l][r] min(dp[l 1][r], dp[l][r - 1]) 1; } } return dp[0][n - 1]; } };3. 心得区间 DP 的状态设计这类题的关键在于把问题落到一个区间上思考。这里用dp[l][r]表示子串区间的最优解就能很自然地根据两端字符是否相等来分类讨论。转移本质当s[l] s[r]时不需要额外插入字符两端直接配对问题规模缩小到内部区间当s[l] ! s[r]时本质上是在“让左端去匹配”还是“让右端去匹配”之间做选择所以取两种方案的较小值再加1。初始化细节长度为1的区间天然是回文串因此默认初始化为0即可。长度为2的区间需要单独处理相同则不需要插入不同则只需要插入1次。遍历顺序当前状态dp[l][r]依赖dp[l 1][r - 1]、dp[l 1][r]和dp[l][r - 1]所以外层必须让l从大到小枚举内层让r从小到大扩展。4. 相关题目LeetCode 516. 最长回文子序列LeetCode 5. 最长回文子串LeetCode 664. 奇怪的打印机