代码随想录算法训练营 Day40 | 动态规划 part13

647. 回文子串给你一个字符串s请你统计并返回这个字符串中 回文子串 的数目。回文字符串 是正着读和倒过来读一样的字符串。子字符串 是字符串中的由连续字符组成的一个序列。class Solution { public: int countSubstrings(string s) { int n s.size(); vectorvectorbool dp(n, vectorbool(n, false)); int res 0; // 【细节1完美的下三角遍历】 // 必须从下往上i从n-1开始因为 dp[i][j] 依赖它左下方的 dp[i1][j-1] // 内层 j 从 i 开始直接舍弃了 j i 的无意义右上角区域 for(int i n - 1; i 0; i--) { for(int j i; j n; j) { if(s[i] s[j]) { // 【细节2优雅的边界合并】 // j - i 1 这个神级条件把两种情况完美合二为一 // 1. j i (长度为1的单字符本身就是回文) // 2. j - i 1 (长度为2的相邻字符如aa只要相等就是回文) // 这两种情况都不需要去越界访问 dp[i1][j-1] if(j - i 1) { res; dp[i][j] true; } else if(dp[i1][j-1]) { // 长度大于2依赖内部子串是否为回文 res; dp[i][j] true; } } // 如果 s[i] ! s[j]dp[i][j] 默认就是 false根本不用写 else } } return res; } };总结1. 单串区间 DP从这道题开始不再是两个字符串比来比去而是在一个字符串内部截取区间[i, j]研究这个区间的性质。状态定义dp[i][j]代表闭区间[i, j]内的子串是否为回文串bool类型。目标函数统计矩阵中true的个数。2. 状态转移方程判断[i, j]是不是回文首要条件是两头字符必须相等s[i] s[j]。相等之后按区间长度分三种情况长度为 1i j单字符必然是回文。长度为 2j - i 1如aa两头相等就是回文。长度 2j - i 1如abca两头相等还不够必须看抠掉两头后的内部区间dp[i1][j-1]是不是回文。3. 遍历顺序这是区间 DP 和普通二维 DP 的最大区别。普通 DP如编辑距离从左上往右下遍历。区间 DP因为dp[i][j]依赖它正左下方的dp[i1][j-1]所以必须保证算[i, j]的时候它下面的行已经算完了。铁律外层i倒序遍历从下往上内层j正序遍历从左往右且j i跳过无意义右上角。516. 最长回文子序列给你一个字符串s找出其中最长的回文子序列并返回该序列的长度。子序列定义为不改变剩余字符顺序的情况下删除某些字符或者不删除任何字符形成的一个序列。class Solution { public: int longestPalindromeSubseq(string s) { int n s.size(); vectorvectorint dp(n, vectorint(n, 0)); // 【细节1精准的初始化】 // 上一题求bool默认false就行。这题求长度单个字符本身就是长度为1的回文序列 for(int i 0; i n; i) dp[i][i] 1; // 【细节2极致的内层起点】 // 上一题 j 从 i 开始。这题因为 dp[i][i] 已经手动初始化过了 // 所以内层直接 j i 1 开始省去了一次无意义的 if 判断 for(int i n - 1; i 0; i--) { for(int j i 1; j n; j) { if(s[i] s[j]) { // 两头相等直接把它俩包进去长度 2 dp[i][j] dp[i1][j-1] 2; } else { // 两头不相等只能扔掉一头。扔掉左头看右边扔掉右头看左边取最大值 // 【核心警醒】这里和 1143(最长公共子序列) 的逻辑一模一样 dp[i][j] max(dp[i1][j], dp[i][j-1]); } } } // 【细节3返回值】 // 上一题是统计全图 true 个数。这题求的是整个串 [0, n-1] 的最大长度 return dp[0][n-1]; } };总结1. “子串” vs “子序列”的 else 分支区别647. 回文子串要求必须连续。如果s[i] ! s[j]这区间绝对不可能是回文子串了直接false啥也不用干。516. 回文子序列只要求相对顺序可以不连续。如果s[i] ! s[j]大区间不行不代表内部没有短的回文序列所以你要找次大区间max(dp[i1][j], dp[i][j-1])。2. 揭开伪装它其实就是 1143 题把原串s正着写一遍再倒着写一遍得到s_rev。求s和s_rev的最长公共子序列LCS就是s的最长回文子序列代码的else分支max(dp[i1][j], dp[i][j-1])和 1143 题一模一样因为本质都是“跳过一个不匹配的字符”。动态规划章节总结一、背包问题01背包 vs 完全背包一维优化下类型遍历顺序要求原因01背包 (物品不重复)外层物品正序内层容量倒序倒序保证每个物品在同一轮只被选1次完全背包 (物品无限)外层物品正序内层容量正序正序允许同一物品在本轮被反复叠加求组合数 vs 求排列数仅限完全背包目标遍历顺序要求经典题目组合数 (不讲究顺序)外层物品内层容量518.零钱兑换II排列数 (讲究顺序)外层容量内层物品377.组合总和IV二、打家劫舍万能公式dp[i] max(dp[i-1], dp[i-2] 当前金额)线性 (198)直接套公式。环形 (213)分类讨论破环 → 结果 max(算[0, n-2], 算[1, n-1])。树形 (337)后序遍历返回数组[不偷当前, 偷当前]递归推导。三、股票问题层级题号与名称改动点核心逻辑 / 状态变化核心公式 / 代码动作Lv1121. 最佳时机(只买1次)限制交易次数为1买入前绝对没有历史利润利润被强制死锁为 0持有 max(昨天持有, 0 - p[i])Lv2122. 最佳时机 II(无限次)解除次数限制万能公式原貌买入时可直接用历史利润抵扣成本持有 max(昨天持有, dp[i-1][0] - p[i])Lv3714. 含手续费(无限次扣钱)每次交易收手续费不要在买入时扣 统一在“卖出”瞬间扣钱最干净不持有 max(昨天不持有, 昨天持有 p[i] - fee)Lv4309. 含冷冻期(无限次时间限制)卖出后隔一天才能买万能公式失效拆分“不持有”状态显式切断转移路径拆为保持不持有、今天卖出、冷冻期。推导“持有”时只允许从“保持不持有”转入。Lv5123. 最佳时机 III(最多2次)限制最多2次状态维度爆炸(变4个1买/1卖/2买/2卖)核心是利润复用2买 max(昨天2买, 1卖 - p[i])(用1卖的利润抵扣2买的成本)Lv6188. 最佳时机 IV(最多k次)2次变任意k次不再手写状态开2k1长度数组用奇偶步长法则一网打尽奇数下标管买dp[j] max(dp[j], dp[j-1] - p[i])偶数下标管卖dp[j] max(dp[j], dp[j-1] p[i])(循环步长j 2)四、子序列问题if (s[i] t[j])匹配时99%的题直接继承左上dp[i-1][j-1]或1。唯一例外 (115题求方案数)左上 正上 (dp[i-1][j-1] dp[i-1][j])。else (s[i] ! t[j])不匹配时看图找方向只能删t→ 只看左dp[i][j-1](392)只能删s→ 只看上dp[i-1][j](115)都能删 → 看左和上取max (1143, 583)能替换 → 看左、上、左上取min1(72)五、回文问题遍历因为依赖左下角dp[i1][j-1]所以外层i倒序内层j正序。代码偷懒技巧if (j - i 1)直接把“单字符”和“双字符aa”两种回文情况合并处理不用越界判断。六、初始化求什么dp[0]或dp[0][j]怎么初始化典型反例求方案数 / 组合数必须初始化为1518零钱兑换、115不同子序列空串也是一种方案求最小步数 / 操作数必须初始化为0, 1, 2...72编辑距离把另一个串全删光的代价求最大长度 / 最大值初始化为01143公共子序列、516回文子序列