[!info] related notes 算法面试题型 MOC 动态规划 最长回文子串 最长回文子序列 买卖股票的最佳时机 股票最大资产

区间 DP 与状态机 DP

1. 区间 DP

一页式速查表

小类	常见状态	转移关键词	入门题	进阶题
区间真假 / 长度	dp[i][j]	看内部区间	[[longest-palindromic-substring	最长回文子串]]
区间最优值	dp[l][r]	枚举最后一步 / 分割点	回文类	[[burst-balloons
状态机两状态	dp[i][state]	持股 / 不持股	[[best-time-to-buy-and-sell-stock	股票入门]]
状态机多状态	dp[i][state]	冷冻 / 交易次数 / 多状态切换	[[best-time-to-buy-and-sell-stock-with-cooldown	冷冻期]]

一句话

当状态和区间 [l, r] 有关时，通常考虑区间 DP。

识别信号

• 子串 / 子数组 / 子区间
• 要判断整个区间是否满足某性质
• 要合并区间、切开区间、枚举分割点

常见状态

dp[l][r] = 区间 [l, r] 的最优值 / 是否满足条件

最常见顺序

按区间长度从小到大。

样例：最长回文子串

题目：最长回文子串

状态

dp[i][j] 表示 s[i...j] 是否为回文串。

转移

dp[i][j] = (s[i] === s[j]) && (j - i <= 1 || dp[i + 1][j - 1])

为什么这样遍历

因为依赖内部更短的区间 dp[i + 1][j - 1]，所以要先算短区间，再算长区间。

高频坑

• 没按区间长度枚举，导致依赖项还没算出来
• 忘了处理长度为 1 或 2 的小区间边界

2. 状态机 DP

一句话

如果题目里“每一步 / 每一天”有若干种状态，并且状态之间会切换，就考虑状态机 DP。

识别信号

• 股票买卖
• 今天能做几种动作
• 当前是否持有、是否冷冻、是否刚卖出

典型状态

dp[i][0] = 第 i 天结束后不持股的最大收益
dp[i][1] = 第 i 天结束后持股的最大收益

基础股票转移

dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i])
dp[i][1] = max(dp[i - 1][1], -prices[i])

如果有限制（手续费、冷冻期、最多交易 k 次），就在状态维度里继续加条件。

样例：股票最大资产

题目：[[interview-max-asset-stock-trading|股票最大资产]]

这类题的关键不是“当前位置选或不选”，而是：

• 当前持有多少股 / 是否持股
• 今天买、卖、还是不动

高频坑

• 状态定义不完整，导致转移写不全
• 把“今天结束后的状态”误写成“今天开始前的状态”
• 忘记给非法状态初始化成负无穷

推荐继续练

• 区间 DP：最长回文子串、最长回文子序列、戳气球
• 状态机 DP：买卖股票的最佳时机、含冷冻期、含手续费、k 次交易、股票最大资产