企业官网建设流程全解析

• 教程
• 文档

状态机 DP（State 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 <= 100，0 <= 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 参考实现（Java）

class 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. 最长定差子序列

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; Map<Integer, 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; Map<Integer, 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 —— 记忆化搜索、双向状态机、矩阵快速幂

552. 学生出勤记录 II（困难） 是状态机 DP 的集大成者，原题解给出了从记忆化搜索到状态机 DP、再到矩阵快速幂的完整递进链条。出勤记录只含'A'（缺勤）、'L'（迟到）、'P'（到场）三种字符，学生能获得奖励需同时满足：缺勤（'A'）严格少于 2 天；不存在连续 3 天及以上迟到（'L'）。给定长度n（1 <= 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（剩余待决策位数）、acnt（A总次数）、lcnt（结尾连续L次数），并记忆化缓存cache[u][acnt][lcnt]：

class Solution { int mod = (int)1e9+7; 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 == 0）：f[i][j][0] += f[i-1][j-1][k']，k' ∈ {0,1,2}；
• 当前位填L（需k != 0）：f[i][j][k] += f[i-1][j][k-1]；
• 当前位填P（需k == 0）：f[i][j][0] += f[i-1][j][k']，k' ∈ {0,1,2}。

// 从 f[u][acnt][lcnt] 往回找所依赖的状态 class Solution { int mod = (int)1e9+7; 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)1e9+7; 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)1e9+7; 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. 多米诺和托米诺平铺 —— 四状态转移

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)1e9+7; 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 转移

801. 使序列递增的最小交换次数（困难） 是状态机 DP 中"求最小代价"的典型：两个等长数组nums1、nums2，一次操作可交换nums1[i]与nums2[i]，求使两数组都严格递增所需的最小交换次数（用例保证可达成，2 <= nums1.length <= 10^5）。因为交换只发生在同一下标，从前往后处理时只需比较当前位置与前一位置的大小关系。

定义f[i][j]：考虑下标范围[0, i]，位置i的交换状态为j（0不交换、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 通用四步法

1. 抽象状态维度：找出决定"当前选择是否合法/当前代价"的离散变量（如偷不偷、颜色、acnt、lcnt、列覆盖形态），把每个组合作为状态j；
2. 写出转移规则：明确每个状态能由哪些前置状态转移而来（往回看），或能更新哪些后继状态（往前推），二者等价，选顺手的实现；
3. 设定边界与初始化：f[0][...]的合法初值、非法状态（正无穷 / 0），以及最终答案取哪个状态（如max(f[n][0], f[n][1])、min(f[n-1][0], f[n-1][1])）；
4. 按需优化：先确认"当前状态只依赖上一位置状态"，再套滚动数组；若转移为线性且n极大，可上矩阵快速幂；若前驱查找复杂，用哈希表记录"值 → 下标/长度"。

8.2 本专题 6 道题的横向对照

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 往往与这些模型交替出现。

• 教程
• 文档