教程文档【免费下载链接】LogicStack-LeetCode公众号「宫水三叶的刷题日记」刷穿 LeetCode 系列文章源码项目地址https://gitcode.com/gh_mirrors/lo/LogicStack-LeetCode点击查看免费下载状态机 DPState Machine DP是动态规划中极具规律性的一类模型它把每个位置可能处于的若干情况显式建模为状态再根据题目约束在状态之间建立转移关系从而把看似复杂的决策过程转化为可递推的状态转移。本文以仓库 Index/状态机 DP.md 索引的 6 道题目为骨架系统讲解状态机 DP 的状态定义范式、两种转移方向、滚动数组优化以及进阶的状态机 哈希表状态机 矩阵快速幂组合技法。读完本文你将掌握一套可复用的状态机 DP 解题模板能够独立分析相邻约束计数取模平铺方案最小交换次数等典型场景。一、状态机 DP 的本质把决策选项变成状态维度普通线性 DP 的状态通常只刻画处理到第几个元素如f[i]而状态机 DP 会在此基础上额外引入一维当前处于哪种情况形成f[i][j]的二维或更高维结构其中j代表该位置的离散状态。以入门题 198. 打家劫舍中等 为例定义f[i][j]为考虑前i间房子、且第i间房子的状态为j时能取得的最大价值其中j 0代表不偷该房子j 1代表偷该房子。由于相邻房子不能同时被偷天然形成两个状态之间的互斥转移。为什么需要这个额外的状态维度因为相邻约束决定了当前选择会受上一位置选择的影响当前房子偷不偷取决于上一间房子偷没偷。把偷/不偷抽象成两个节点两个节点之间只有允许的边可以转移这就是状态机的直观含义。状态机 DP 的通用识别特征决策具有相邻/连续约束如相邻不能同时连续不能超过 k 次相邻颜色不能相同当前状态只依赖有限个离散取值如{偷, 不偷}、{红, 蓝, 绿}、{A 出现 0/1 次} × {连续 L 0/1/2 次}转移规则可以用一张状态 → 后继状态的有向图描述。二、入门第一题198. 打家劫舍 —— 二状态状态机的完整推导2.1 题目与状态定义你是一个专业小偷沿街房屋每间藏有现金相邻房屋装有联动防盗系统两间相邻房屋在同一晚被闯入会报警。给定非负整数数组nums求不触发警报前提下能偷到的最高金额1 nums.length 1000 nums[i] 400。定义f[i][j]考虑前i间房子第i间房子状态为j时的最大价值j 0不偷j 1偷。2.2 转移方程推导当前房子不偷f[i][0]对前一间房子无任何要求直接取前一状态的最大值f[i][0] max(f[i-1][0], f[i-1][1])当前房子偷f[i][1]此时限定前一间只能不偷价值等于前一间不偷的价值 当前房子金额f[i][1] f[i-1][0] nums[i-1]最终答案为max(f[n][0], f[n][1])。注意这里nums下标从 0 开始而状态下标从 1 开始因此取nums[i-1]。2.3 参考实现Javaclass Solution { public int rob(int[] nums) { int n nums.length; int[][] f new int[n 10][2]; for (int i 1; i n; i) { f[i][0] Math.max(f[i - 1][0], f[i - 1][1]); f[i][1] f[i - 1][0] nums[i - 1]; } return Math.max(f[n][0], f[n][1]); } }时间复杂度O(n)空间复杂度O(n)。同题的 C / TypeScript / Python 完整实现见 198. 打家劫舍中等.md。2.4 滚动数组优化至 O(1) 空间由于f[i][X]只依赖f[i-1][X]可以用「滚动数组」把二维表压缩为两行交替复用。这是状态机 DP 最常用的空间优化手段class Solution { public int rob(int[] nums) { int n nums.length; int[][] f new int[][]{{0, 0}, {0, 0}}; for (int i 1; i n; i) { int a (i - 1) 1, b i 1; f[b][0] Math.max(f[a][0], f[a][1]); f[b][1] f[a][0] nums[i - 1]; } return Math.max(f[n 1][0], f[n 1][1]); } }时间复杂度O(n)空间复杂度O(1)。三、经典多状态模型剑指 Offer II 091. 粉刷房子 —— 状态互斥转移剑指 Offer II 091. 粉刷房子中等 将状态数从 2 扩展到 3且要求相邻房子颜色不能相同状态互斥。有n个房子排成一排每个房子可刷成红、蓝、绿三种颜色之一相邻房子颜色不能相同costs[i][j]表示第i号房子刷成第j种颜色的成本求粉刷完所有房子的最小花费。定义f[i][j]考虑下标不超过i的房子最后一间房子颜色为j时的最小成本。初始化f[0][i] cs[0][i]只有第一间房子时成本即其自身上色成本。转移时f[i][j]等于所有f[i-1][prev]prev ! j的最小值加上cs[i][j]——当前颜色与前一间颜色必须不同。由于f[i][X]只依赖f[i-1][X]可直接用三个变量a、b、c代替动规数组本质仍是滚动思想class Solution { public int minCost(int[][] cs) { int n cs.length; int a cs[0][0], b cs[0][1], c cs[0][2]; for (int i 1; i n; i) { int d Math.min(b, c) cs[i][0]; int e Math.min(a, c) cs[i][1]; int f Math.min(a, b) cs[i][2]; a d; b e; c f; } return Math.min(a, Math.min(b, c)); } }时间复杂度O(n × C)其中C 3为颜色数量空间复杂度O(1)。这一题的要点在于某些状态只能由规则限定的状态所转移——即状态机 DP 的核心判据。既可以正向思考从f[i][j]能更新哪些后继状态也可以反向思考f[i][j]依赖哪些前驱状态两种方向殊途同归。四、状态机 哈希表1218. 最长定差子序列最长定差子序列中等 展示了状态机 DP 与哈希表、贪心结合的玩法。给定整数数组arr和整数difference求相邻元素之差恒等于difference的最长子序列长度1 arr.length 10^5-10^4 arr[i], difference 10^4。4.1 二维状态版本区分选/不选定义f[i][j]j非 0 即 1考虑前i个数第i个数的选择情况为j时的最长定差子序列长度。初始化f[0][0] 0、f[0][1] 1答案为max(f[n-1][0], f[n-1][1])。f[i][0]第i个不选f[i][0] max(f[i-1][0], f[i-1][1])f[i][1]第i个要选要么独立成子序列值为 1要么接到某个数后面——给定差值后可直接算出上一个值prev arr[i] - difference找到值为prev且下标最大的位置转移过来f[i][1] f[hash[prev]][1] 1。这里的贪心正确性在于若存在多个值为prev的位置选择下标最大的那个小于i进行转移结果不会比选其他位置更差因为定差子序列只关心前驱的值下标越靠后越容易在后续接上更多元素。因此转移过程中用哈希表记录值 → 最新下标。class Solution { public int longestSubsequence(int[] arr, int d) { int n arr.length; MapInteger, Integer map new HashMap(); int[][] f new int[n][2]; f[0][1] 1; map.put(arr[0], 0); for (int i 1; i n; i) { f[i][0] Math.max(f[i - 1][0], f[i - 1][1]); f[i][1] 1; int prev arr[i] - d; if (map.containsKey(prev)) f[i][1] Math.max(f[i][1], f[map.get(prev)][1] 1); map.put(arr[i], i); } return Math.max(f[n - 1][0], f[n - 1][1]); } }4.2 优化状态定义一维 哈希表直接完成必选转移多定义一维状态是为了正确转移出第i位被选择的情况但利用哈希表本身就能做到调整定义为f[i]为考虑前i个数第i个数必选时的最长定差子序列长度转移即f[i] hash[prev] 1哈希表初始化为 0表示没有任何前驱时的长度 0。class Solution { public int longestSubsequence(int[] arr, int d) { int ans 1; MapInteger, Integer map new HashMap(); for (int i : arr) { map.put(i, map.getOrDefault(i - d, 0) 1); ans Math.max(ans, map.get(i)); } return ans; } }由于值域有限±10^4还可以直接用数组充当哈希表N 40009、M N / 2用hash[x M]完成下标偏移映射把单次转移压到O(1)且无哈希开销。两种实现HashMap 版与数组版的完整代码见 1218. 最长定差子序列中等.md。时间复杂度O(n)空间复杂度O(n)。五、进阶组合552. 学生出勤记录 II —— 记忆化搜索、双向状态机、矩阵快速幂学生出勤记录 II困难 是状态机 DP 的集大成者原题解给出了从记忆化搜索到状态机 DP、再到矩阵快速幂的完整递进链条。出勤记录只含A缺勤、L迟到、P到场三种字符学生能获得奖励需同时满足缺勤A严格少于 2 天不存在连续 3 天及以上迟到L。给定长度n1 n 10^5返回可奖励记录数量对10^9 7取余。5.1 基本分析识别状态机的两个关键量合法方案中A总出现次数最多 1 次、L连续出现次数最多 2 次。因此决策某一位选什么时只关心当前方案里已经出现多少个A决定能否再填A以及结尾连续L的次数决定能否再填L——这正是状态机的两个维度acnt ∈ [0,1]lcnt ∈ [0,2]共2 × 3 6个状态。5.2 记忆化搜索版本先写爆搜 DFS参数u剩余待决策位数、acntA总次数、lcnt结尾连续L次数并记忆化缓存cache[u][acnt][lcnt]class Solution { int mod (int)1e97; int[][][] cache; public int checkRecord(int n) { cache new int[n 1][2][3]; for (int i 0; i n; i) { for (int j 0; j 2; j) { for (int k 0; k 3; k) { cache[i][j][k] -1; } } } return dfs(n, 0, 0); } int dfs(int u, int acnt, int lcnt) { if (acnt 2) return 0; if (lcnt 3) return 0; if (u 0) return 1; if (cache[u][acnt][lcnt] ! -1) return cache[u][acnt][lcnt]; int ans 0; ans dfs(u - 1, acnt 1, 0) % mod; // A ans (ans dfs(u - 1, acnt, lcnt 1)) % mod; // L ans (ans dfs(u - 1, acnt, 0)) % mod; // P cache[u][acnt][lcnt] ans; return ans; } }时间复杂度O(n * 2 * 3) O(n)空间复杂度O(n)。5.3 状态机 DP两种方向的实现记忆化搜索揭示了本质状态f[u][acnt][lcnt]只会被特定状态更新也只会更新特定状态——这就是状态机模型的 DP。据此可以写出两个方向的递推方向一从f[u][acnt][lcnt]往回找依赖的状态当前状态 前一位各合法前置状态之和当前位填A需j 1 k 0f[i][j][0] f[i-1][j-1][k]k ∈ {0,1,2}当前位填L需k ! 0f[i][j][k] f[i-1][j][k-1]当前位填P需k 0f[i][j][0] f[i-1][j][k]k ∈ {0,1,2}。// 从 f[u][acnt][lcnt] 往回找所依赖的状态 class Solution { int mod (int)1e97; public int checkRecord(int n) { int[][][] f new int[n 1][2][3]; f[0][0][0] 1; for (int i 1; i n; i) { for (int j 0; j 2; j) { for (int k 0; k 3; k) { if (j 1 k 0) { // A f[i][j][k] (f[i][j][k] f[i - 1][j - 1][0]) % mod; f[i][j][k] (f[i][j][k] f[i - 1][j - 1][1]) % mod; f[i][j][k] (f[i][j][k] f[i - 1][j - 1][2]) % mod; } if (k ! 0) { // L f[i][j][k] (f[i][j][k] f[i - 1][j][k - 1]) % mod; } if (k 0) { // P f[i][j][k] (f[i][j][k] f[i - 1][j][0]) % mod; f[i][j][k] (f[i][j][k] f[i - 1][j][1]) % mod; f[i][j][k] (f[i][j][k] f[i - 1][j][2]) % mod; } } } } int ans 0; for (int j 0; j 2; j) { for (int k 0; k 3; k) { ans f[n][j][k]; ans % mod; } } return ans; } }方向二从f[u][acnt][lcnt]出发往前更新能到达的状态由当前状态累加贡献到后继状态// 从 f[u][acnt][lcnt] 出发往前去更新所能更新的状态值 class Solution { int mod (int)1e97; public int checkRecord(int n) { int[][][] f new int[n 1][2][3]; f[0][0][0] 1; for (int i 0; i n; i) { for (int j 0; j 2; j) { for (int k 0; k 3; k) { if (j ! 1) f[i 1][j 1][0] (f[i 1][j 1][0] f[i][j][k]) % mod; // A if (k ! 2) f[i 1][j][k 1] (f[i 1][j][k 1] f[i][j][k]) % mod; // L f[i 1][j][0] (f[i 1][j][0] f[i][j][k]) % mod; // P } } } int ans 0; for (int j 0; j 2; j) { for (int k 0; k 3; k) { ans f[n][j][k]; ans % mod; } } return ans; } }时间复杂度O(n)空间复杂度O(n)。5.4 矩阵快速幂把线性递推加速到 O(log n)强调往回/往前的更新方向是因为存在线性关系且满足结合律的递推式可以用矩阵快速幂加速。这里acnt、lcnt的组合状态只有 6 种用idx acnt * 3 lcnt做二维转一维idx 0..5分别对应(0,0)、(0,1)、(0,2)、(1,0)、(1,1)、(1,2)。最终答案ans Σ f[n][idx]idx 0..5。把答案依赖的状态整理成列向量g[n]根据状态机逻辑可得g[n] mat * g[n-1]其中转移矩阵mat [ 1 1 1 0 0 0 ] [ 1 0 0 0 0 0 ] [ 0 1 0 0 0 0 ] [ 1 1 1 1 1 1 ] [ 0 0 0 1 0 0 ] [ 0 0 0 0 1 0 ]由矩阵乘法的结合律g[n] mat^n * g[0]其中g[0]只有f[0][0] 1一个非零分量列向量{1,0,0,0,0,0}。对mat^n套用快速幂即可在O(log n)内完成计算class Solution { int N 6; int mod (int)1e97; long[][] mul(long[][] a, long[][] b) { int r a.length, c b[0].length, z b.length; long[][] ans new long[r][c]; for (int i 0; i r; i) { for (int j 0; j c; j) { for (int k 0; k z; k) { ans[i][j] a[i][k] * b[k][j]; ans[i][j] % mod; } } } return ans; } public int checkRecord(int n) { long[][] ans new long[][]{ {1}, {0}, {0}, {0}, {0}, {0} }; long[][] mat new long[][]{ {1, 1, 1, 0, 0, 0}, {1, 0, 0, 0, 0, 0}, {0, 1, 0, 0, 0, 0}, {1, 1, 1, 1, 1, 1}, {0, 0, 0, 1, 0, 0}, {0, 0, 0, 0, 1, 0} }; while (n ! 0) { if ((n 1) ! 0) ans mul(mat, ans); mat mul(mat, mat); n 1; } int res 0; for (int i 0; i N; i) { res ans[i][0]; res % mod; } return res; } }时间复杂度O(log n)空间复杂度O(1)。本题三种解法完整收录于 552. 学生出勤记录 II困难.md是同一模型从朴素到极致的复杂度演化的最佳范本。六、几何化视角790. 多米诺和托米诺平铺 —— 四状态转移多米诺和托米诺平铺中等 用2 x 1的多米诺骨牌和L形托米诺骨牌均可旋转平铺2 x n面板求方案数对10^9 7取模1 n 1000。骨牌不能溢出棋盘两端这让当前列覆盖状态成为天然的状态机维度。定义f[i][j]无须考虑前i-1列已铺满当前第i列状态为j时的方案数其中j ∈ [0,4)表示当前列四种填充情况0不放置、1竖放一块1 x 2骨牌列被铺满、2与3对应两种被L形骨牌占据的中间形态。初始状态f[1][0] f[1][1] 1第一列不放、或竖放一块骨牌f[1][2] f[1][3] 0棋盘左侧之外无法放置骨牌不合法最终答案取f[n][1]所有列恰好铺满不溢出右侧。分情况讨论转移务必注意留空第i-1列再竖放骨牌的决策只影响第i-1列其方案数已在f[i-1][X]统计过因此f[i][0]只能由f[i-1][1]转移而来不能由f[i-1][0]转移f[i][0] f[i-1][1]f[i][1] Σ f[i-1][j]j ∈ [0,4)f[i][2] f[i-1][0] f[i-1][3]f[i][3] f[i-1][0] f[i-1][2]。class Solution { int MOD (int)1e97; public int numTilings(int n) { int[][] f new int[n 10][4]; f[1][0] f[1][1] 1; for (int i 2; i n; i) { f[i][0] f[i - 1][1]; int cur 0; for (int j 0; j 4; j) cur (cur f[i - 1][j]) % MOD; f[i][1] cur; f[i][2] (f[i - 1][0] f[i - 1][3]) % MOD; f[i][3] (f[i - 1][0] f[i - 1][2]) % MOD; } return f[n][1]; } }时间复杂度O(n)空间复杂度O(n)。同样由于f[i][X]只依赖f[i-1][X]可用滚动数组把空间压到O(1)int[][] f new int[2][4]按i 1交替读写返回f[n 1][1]完整代码Java/C/Python/TypeScript见 790. 多米诺和托米诺平铺中等.md。本题的启示是平铺类问题的列覆盖状态天然是状态机维度只需为每一种半铺/全铺形态分配一个状态即可机械地写出转移。七、最小化类状态机801. 使序列递增的最小交换次数 —— min 转移使序列递增的最小交换次数困难 是状态机 DP 中求最小代价的典型两个等长数组nums1、nums2一次操作可交换nums1[i]与nums2[i]求使两数组都严格递增所需的最小交换次数用例保证可达成2 nums1.length 10^5。因为交换只发生在同一下标从前往后处理时只需比较当前位置与前一位置的大小关系。定义f[i][j]考虑下标范围[0, i]位置i的交换状态为j0不交换、1交换时两数组满足严格递增的最小交换次数。初始化f[0][0] 0、f[0][1] 1其余未知状态初始化为正无穷答案为min(f[n-1][0], f[n-1][1])。转移分两类顺序位满足nums1[i] nums1[i-1]且nums2[i] nums2[i-1]两个位置要么都不交换、要么都交换f[i][0] f[i-1][0]f[i][1] f[i-1][1] 1交叉位满足nums1[i] nums2[i-1]且nums2[i] nums1[i-1]两个位置只能有其一交换f[i][0] min(f[i][0], f[i-1][1])f[i][1] min(f[i][1], f[i-1][0] 1)class Solution { public int minSwap(int[] nums1, int[] nums2) { int n nums1.length; int[][] f new int[n][2]; for (int i 1; i n; i) f[i][0] f[i][1] n 10; f[0][1] 1; for (int i 1; i n; i) { if (nums1[i] nums1[i - 1] nums2[i] nums2[i - 1]) { f[i][0] f[i - 1][0]; f[i][1] f[i - 1][1] 1; } if (nums1[i] nums2[i - 1] nums2[i] nums1[i - 1]) { f[i][0] Math.min(f[i][0], f[i - 1][1]); f[i][1] Math.min(f[i][1], f[i - 1][0] 1); } } return Math.min(f[n - 1][0], f[n - 1][1]); } }时间复杂度O(n)空间复杂度O(n)。本题同样可滚动数组优化至O(1)空间用两个变量承接min结果再写回完整实现见 801. 使序列递增的最小交换次数困难.md。注意未知状态初始化为正无穷这一细节——min类状态机 DP 必须用足够大的占位值保证非法路径不被选中。八、方法总结状态机 DP 的四步套路与优化工具箱8.1 通用四步法抽象状态维度找出决定当前选择是否合法/当前代价的离散变量如偷不偷、颜色、acnt、lcnt、列覆盖形态把每个组合作为状态j写出转移规则明确每个状态能由哪些前置状态转移而来往回看或能更新哪些后继状态往前推二者等价选顺手的实现设定边界与初始化f[0][...]的合法初值、非法状态正无穷 / 0以及最终答案取哪个状态如max(f[n][0], f[n][1])、min(f[n-1][0], f[n-1][1])按需优化先确认当前状态只依赖上一位置状态再套滚动数组若转移为线性且n极大可上矩阵快速幂若前驱查找复杂用哈希表记录值 → 下标/长度。8.2 本专题 6 道题的横向对照题目状态维度转移特点优化技法推荐指数198. 打家劫舍2偷/不偷相邻互斥滚动数组 → O(1)剑指 Offer II 091. 粉刷房子3三色相邻颜色互斥三变量代替数组1218. 最长定差子序列2 → 1差值定向 贪心哈希表 / 数组哈希552. 学生出勤记录 II2 × 3 6计数约束 双向转移记忆化 → 状态机 → 矩阵快速幂790. 多米诺和托米诺平铺4列覆盖形态平铺形态接力滚动数组 → O(1)801. 使序列递增的最小交换次数2交换/不交换顺序位/交叉位两类转移滚动数组 → O(1)8.3 何时考虑矩阵快速幂当满足以下条件时状态机 矩阵快速幂可以把O(n)降到O(log n)递推关系是线性的当前状态是前置状态的线性组合、状态数很小可枚举为列向量、n很大如10^5以上或更大数量级。构造方法是先把状态压成一维下标写出g[n] mat * g[n-1]再对mat^n套快速幂。仓库中 552. 学生出勤记录 II困难.md 给出了从 DP 递推到矩阵构造的完整推导过程可当作该技法的标准教材。8.4 继续阅读本专题完整目录索引Index/状态机 DP.md含全部题目的 LeetCode 原题与题解入口六道题的多语言完整代码Java / C / Python / TypeScript分别存放在上述各题解文件中如需系统化按 Tag 刷题可配合仓库 Index 目录下的其他算法索引如 线性 DP.md、序列 DP.md、矩阵快速幂.md联动学习状态机 DP 往往与这些模型交替出现。赞分享教程文档【免费下载链接】LogicStack-LeetCode公众号「宫水三叶的刷题日记」刷穿 LeetCode 系列文章源码项目地址https://gitcode.com/gh_mirrors/lo/LogicStack-LeetCode点击查看免费下载相关推荐动态规划状态转移方程DP问题建模的终极指南与核心技巧动态规划状态转移方程DP问题建模的终极指南与核心技巧 动态规划Dynamic Programming是算法学习中至关重要的概念而状态转移方程则是DP问题文档教程知识库AlgoNote 区间动态规划区间 DP完全指南两类核心模型、状态设计与经典例题精解AlgoNote 区间动态规划区间 DP完全指南两类核心模型、状态设计与经典例题精解 区间动态规划区间 DP是「算法通关手册」AlgoNote动态教程文档知识库动态规划DP算法实战指南从状态定义到状态转移的完整解题框架动态规划DP算法实战指南从状态定义到状态转移的完整解题框架 动态规划Dynamic ProgrammingDP是算法学习中最重要也最考验思维的算法设教程上一篇突破微信网页版限制wechat-need-web插件带来无缝浏览器聊天体验下一篇霞鹜文楷免费开源中文字体如何改变你的中文排版体验创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考