状态机DP
创始人
2025-06-01 18:58:02
状态机DP
- 算法特征
- 子数组类DP问题的定义：以最后一个元素结尾的最大xxx
- 特征1：定义多个子问题
- 特征2：状态是一个连续的过程
算法特征
状态机 DP 和 DP 的区别在于：
- 状态机 DP 单个状态下有多个情况，普通 DP 只有单个情况 -> 所以定义，也从一个子问题变成多个子问题
- 每个状态顺序是一个连续的过程（类似 A->B->C），子问题是相互依赖、交替计算的关系
算例：978. 最长湍流子数组
题解：https://leetcode.cn/problems/longest-turbulent-subarray/solution/yi-zhang-dong-tu-xiang-jie-dong-tai-gui-wrwvn/
拆解一下，解题思路的关键步骤。
子数组类DP问题的定义：以最后一个元素结尾的最大xxx
一、子数组类DP问题的定义：子数组是连续的，子数组类的子问题定义必须加一个限制 — 以最后一个元素结尾的。
- 如最大子数组和：子问题 f(k) 表示 nums[0…k) 中，以最后一个元素结尾的最大子数组和。
特征1：定义多个子问题
978. 最长湍流子数组，一个子问题，有上升和下降、水平三种状态，三种状态组合有五种情况。
f(k) 从哪里来？
为了简化，我们可以定义多个子问题。
定义多个子问题思路就是这样，像状态机DP题是一定要定义多个子问题的。
特征2：状态是一个连续的过程
算例：123. 买卖股票的最佳时机 III
题目限制条件：最多完成俩笔交易。
这意味着，股票买卖的过程，经历了不同的阶段，这就是状态机模式。
俩笔一进一出，有五种阶段：
定义每个阶段状态，以及每个阶段状态从哪里来？
相关内容
热门资讯
昊海生科拟受让瑞济生物19.8...
北京商报讯（记者 丁宁）12月12日晚间，昊海生科（688366）发布公告称，公司拟以自有资金383...
原创 飞...
散瓶批发参考价跌至1485元/瓶，原箱产品报价1495元，较年初价格累计跌幅超30%，曾经一瓶难求的...
王源北京跨晚活动展现独特氛围
近日，王源在北京举办的跨晚活动引发了广泛关注，现场氛围热烈，吸引了众多粉丝的参与。活动于2025年举...
2025年度《财经》长青企业案...
“2026《财经》可持续发展论坛暨长青企业案例发布仪式”即将启幕，敬请期待。 2025年，是“十四五...
迎接飞机“退役潮” 资环绿投与...
天津北方网讯：日前，中国资环旗下资环绿投国际公司与中飞航空后市场控股有限公司（简称“中飞后市场”）正...