给每个位置装上一个「状态」

到目前为止，线性 DP 的每个位置 $i$ 只记一个数： $dp[i]$ 。但很多问题里，「站在位置 $i$ 」并不是一个笼统的局面—— 它还分几种互斥的处境。比如手上有没有股票、第 $i$ 个数选了没选、机器此刻停在哪一档。于是我们给每个位置引入若干离散状态 $s$ ，用 $dp[i][s]$ 分别记录，让转移在状态之间流动——这就是线性状态机 DP。

先看一个最朴素的「受限选取」：给一排数 $a_1,a_2,\dots,a_n$ ，要挑出若干个使总和最大，但有一条硬约束——相邻的两个不能同时选（选了 $a_i$ 就不能选 $a_{i-1}$ 和 $a_{i+1}$ ）。这正是「打家劫舍」式的模型。

受限选取：a=[1,2,3,1]，相邻两数用红虚线连着表示互斥。选 a1+a3=1+3=4 是最大——不能贪心地把最大的 3 和它两边一起拿。

为什么不能贪心地「从大到小挑，冲突就跳过」？看最短的反例 $a=[1,2,3]$ ：贪心先拿最大的 $3$ （在中间），它左右两个数就都被禁了，只得 $3$ ；可最优是拿两端 $a_1+a_3=1+3=4$ 。贪心为了眼前那个大数，堵死了两侧更划算的组合。此刻选或不选，牵动前后两侧——又是需要 DP 的信号。而枚举「每个数选或不选」的所有组合是 $2^n$ 种， $n=50$ 就已无从枚举。

状态与转移：选，还是不选

定状态。光记「前 $i$ 个的最大和」不够——因为下一步能不能选 $a_{i+1}$ ，取决于 $a_i$ 到底选没选。于是把这个「选没选」显式记进状态：设 $dp[i][0]$ = 考虑前 $i$ 个、且不选 $a_i$ 时的最大和； $dp[i][1]$ = 前 $i$ 个、且选 $a_i$ 时的最大和。

两状态之间的转移：不选 dp[i][0] 可承接上一位置的任一状态（取 max）；选 dp[i][1] 只能接上一位置的「不选」——这条独木桥正是「相邻互斥」的化身。

不选 $a_i$ （ $dp[i][0]$ ）：既然本位不取，前一个 $a_{i-1}$ 选或不选都行，所以从上一位置的两个状态里取较大者：

dp[i][0]=\max\big(dp[i-1][0],\ dp[i-1][1]\big)

选 $a_i$ （ $dp[i][1]$ ）：本位既然要取，前一个 $a_{i-1}$ 就必须不选（相邻互斥），只能接上一位置的「不选」状态，再加上 $a_i$ 自己：

dp[i][1]=dp[i-1][0]+a_i

边界： $dp[0][0]=dp[0][1]=0$ （哨兵起点，什么都没考虑）。答案在末列取两状态较大者——因为最后一个数选不选都可以：

\text{ans}=\max\big(dp[n][0],\ dp[n][1]\big)

本质：状态，就是「决策的记忆」

普通线性 DP 的 $dp[i]$ 只背一个总量；状态机 DP 多出的那一维，背的是「上一步做了什么决定」——正因为把「 $a_i$ 选没选」记进了状态，下一步才知道自己能不能选。它把「后面的决策依赖前面怎么选」这层耦合，拆成了每个状态各自独立、可按位置递推的小问题， $2^n$ 种组合被 $O(n\cdot k)$ （ $k$ 为状态数）装下。

跟着算一遍

用开头的例子 $a=[1,2,3,1]$ 走几步，把两个状态并行推进（下标从 1 记）：

1

第 1 个数（a₁=1）。 不选

dp[1][0]=\max(0,0)=0

；选

dp[1][1]=dp[0][0]+1=0+1=1

。

2

第 2 个数（a₂=2）。 不选

dp[2][0]=\max(dp[1][0],dp[1][1])=\max(0,1)=1

；选

dp[2][1]=dp[1][0]+2=0+2=2

。

3

第 3 个数（a₃=3）。 不选

dp[3][0]=\max(1,2)=2

；选

dp[3][1]=dp[2][0]+3=1+3=4

（接的是「a₂ 不选」那条，即选了 a₁）。

4

第 4 个数（a₄=1）。 不选

dp[4][0]=\max(2,4)=4

；选

dp[4][1]=dp[3][0]+1=2+1=3

。末列取大：

\max(4,3)=4

——正是选

a_1+a_3

的答案，和手算吻合。

下面的演示把

dp[i][0/1]

这张「状态 × 位置」的二维表逐格填满，并高亮每一格在上一位置的来源。改数组、加删元素、或换个预设，看它实时重算。

看两个状态一格一格长出来

当前数组的最大不相邻和：ans = 4 （= 末列 max(不选, 选)，任意两个被选的数下标都不相邻）

起

a1

a2

a3

a4

不选

选

0

·

0

·

当前计算依赖来源被选转移已确定

dp[0][0]=dp[0][1]=0

哨兵起点：尚未考虑元素时，「不选」与「选」两状态的最优值都是 0。

进度

已暂停，第 1 步，共 10 步，1 倍速

深化：股票买卖——把「持有 / 未持有」做成状态机

「选 / 不选」只是最简单的两状态。真正让状态机大显身手的，是股票买卖一族：给出每天的价格 $p_1,\dots,p_n$ ，可以在某天买入、某天卖出（手上最多持一股），求最大利润。关键抓手同样是——站在第 $i$ 天，你此刻「手里有没有股票」是两种截然不同的处境，能做的动作也不同。

于是设两个状态： $\mathit{hold}[i]$ = 第 $i$ 天结束时持有一股的最优现金； $\mathit{cash}[i]$ = 第 $i$ 天结束时空仓的最优现金（现金相对初始 0 计，买入是垫钱、卖出是回款）。

股票状态机：持有(hold) 与未持有(cash) 两节点。买入边把 cash→hold（现金 −price），卖出边把 hold→cash（现金 +price），两个自环是「不动」。若带冷却，卖出后要在 cash 多停一天才能再买入。

逐日在两状态间转移（无限次交易版）：

\mathit{cash}[i]=\max\big(\mathit{cash}[i-1],\ \mathit{hold}[i-1]+p_i\big)

\mathit{hold}[i]=\max\big(\mathit{hold}[i-1],\ \mathit{cash}[i-1]-p_i\big)

前者：空仓 = 昨天就空仓（不动）、或昨天持有今天卖出（ $+p_i$ ）；后者：持有 = 昨天就持有（不动）、或昨天空仓今天买入（ $-p_i$ ）。初始 $\mathit{cash}[0]=0$ 、 $\mathit{hold}[0]=-\infty$ （还没买过）。答案取末日的 $\mathit{cash}[n]$ ——手里不留股才算落袋。

再加一条冷却期（卖出后次日不能买入）会怎样？只需把买入时的现金基准从「昨日空仓」改成「前天空仓」 $\mathit{cash}[i-2]$ ——这样刚卖出的那天就买不回来了。换句话说，加一条规则，只是给状态机换一条边，主干丝毫不动。这正是状态机模型的威力：现实约束越复杂，越能靠「多设一个状态 / 改一条转移边」优雅地容纳。

下面的演示把状态机逐日推演：点某天或用按钮前进，看「持有 / 空仓」两状态的最优现金如何随每天买 / 卖 / 不动更新。改价格、勾上「冷却期」，观察那条被改的边如何影响全局。

逐日推演：点某天或用下方按钮走到第 6 天买 / 卖 / 持 / 空

7

买d1

1

买d2

5

卖d3

3

买d4

6

卖d5

4

买d6

第 6 天（价 4）结束时，两状态的最优现金：

持有一股（hold）

3

手里握着一股时的最优现金（已垫付买入价）。今日由：

今日买入（−4）

空仓（cash）

7

手里没有股票时的最优现金（落袋利润）。今日由：

继续空仓（不动）

走到第 6 天，空仓最优现金 = 7。全程结束——最终答案取空仓态（手里不留股才算落袋）：7。与「逢涨就吃」贪心核对：无限次交易最优利润 = 7，两者一致。

第 6 / 6 天

常见陷阱 · 答案取「空仓」态，别取 max

股票问题最终答案是 $\mathit{cash}[n]$ （末日空仓），不是 $\max(\mathit{hold}[n],\mathit{cash}[n])$ ——手里还攥着一股不叫利润。另一处易错： $\mathit{hold}$ 的初值必须是 $-\infty$ 而非 0，否则「还没买就先算持有」会凭空多出一股。状态机 DP 的边界，往往就藏在这些「哪个状态一开始根本不可能」的细节里。

例题

P2196[NOIP1996 提高组] 挖地雷NOIP1996 提高普及/提高-

题意

n

个地窖各有若干地雷，给出哪些地窖间有地道（只能从编号小走向编号大）。从任一地窖出发一路挖下去，求最多地雷数，并输出具体路径。

为什么选它

状态机 DP 的入门底子：边只朝编号增大的方向 → 天然是一张 DAG，

f[i]

=「从

i

出发最多挖多少」就是最朴素的路径 DP。更重要的是它逼你练方案回溯——多存一个

nxt[i]

记住每步走向谁，再顺链打印。这是「状态里存决策、事后还原路径」的第一课。

转移 · 复杂度

f[i]=a_i+\max_{\,j>i,\ g[i][j]}f[j]

，逆序递推；起点取

\arg\max_i f[i]

；时间

O(n^2)

。

参考代码（逆序 DP + nxt 回溯路径）

C++

在洛谷打开 P2196

#include <iostream>
#include <algorithm>
using namespace std;

int n;
int a[25];                       // 每个地窖的地雷数
bool g[25][25];                  // g[i][j]：i 能否走到 j（题目保证 j>i）
int f[25], nxt[25];              // f[i]：从 i 出发最多能挖的地雷；nxt[i]：路径上 i 的下一个

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i < n; i++)          // 上三角连接矩阵：i 到 i+1..n
        for (int j = i + 1; j <= n; j++)
            cin >> g[i][j];

    int start = 1;
    for (int i = n; i >= 1; i--)         // ★逆序：转移只依赖编号更大的地窖
    {
        f[i] = a[i];                     // 至少挖自己这一窖
        nxt[i] = 0;                      // 0 表示到此为止
        for (int j = i + 1; j <= n; j++)
            if (g[i][j] && a[i] + f[j] > f[i])
            {
                f[i] = a[i] + f[j];      // 接到 j 那条最优链后面
                nxt[i] = j;              // 记下一步，供回溯路径
            }
        if (f[i] > f[start])             // 起点可以是任意地窖，取全局最优
            start = i;
    }

    for (int i = start; i; i = nxt[i])   // 顺着 nxt 链把路径打印出来
        cout << i << (nxt[i] ? " " : "\n");
    cout << f[start] << endl;
    return 0;
}
// TAG: 线性DP DAG路径 状态机 方案回溯

P4310绝世好题洛谷原生普及+/提高

题意

给长度

n

的序列，求最长子序列

b

，使相邻两项按位与不为 0（

b_i\ \&\ b_{i-1}\neq 0

，即至少共享一个为 1 的二进制位）。

换个视角（把状态藏进「位」里）

若沿用 LIS 的「

dp[i]

向左扫所有

j

」是

O(n^2)

，会超时。妙处在于：能不能接只看「有没有公共位」，与具体是哪个数无关。于是不按「下标」记状态，而按二进制位记：

f[b]

= 以「第

b

位为 1 的数」结尾的最长合法子序列长度。处理

a_i

时，它能接的最长链 = 它所有为 1 的位对应

f[b]

的最大值，

+1

后再回写到它每个为 1 的位。是「状态即决策的记忆」的绝佳变体——记忆被压进了 31 个按位状态。

转移 · 复杂度

\mathit{cur}=1+\max_{\,b:\ a_i\ \&\ 2^b\neq 0}f[b]

，再对每个这样的

b

令

f[b]\leftarrow\max(f[b],\mathit{cur})

；时间

O(30n)

。

参考代码（按位状态机 f[bit]）

C++

在洛谷打开 P4310

#include <iostream>
#include <algorithm>
using namespace std;

int n, ans;
int f[35];                       // f[b]：以「第 b 位为 1 的数」结尾的最长合法子序列长度

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        int x;
        cin >> x;

        // 决策的记忆压进 31 个「按位状态」里：
        // b_i & b_{i-1} != 0 ⇔ 两数至少共享一个为 1 的位。
        int best = 0;                    // 能接在谁后面：所有与 x 共位的状态取最大
        for (int b = 0; b < 31; b++)
            if (x >> b & 1)
                best = max(best, f[b]);

        int cur = best + 1;              // x 自己接上去，长度 +1
        for (int b = 0; b < 31; b++)     // x 的每个为 1 的位都被刷新为 cur
            if (x >> b & 1)
                f[b] = max(f[b], cur);

        ans = max(ans, cur);
    }

    cout << ans << endl;
    return 0;
}
// TAG: 线性DP 按位状态机 f[bit]转移 O(30n)

P2569[SCOI2010] 股票交易SCOI2010省选/NOI-

题意

T

天，每天给出买入价

ap_i

、卖出价

bp_i

及单日买入上限

as_i

、卖出上限

bs_i

；任意时刻持股不超过

\max P

；两次交易之间必须间隔 $W$ 天（冷却）。求最大收益。

状态设计（拔高 · 只给思路）

设

f[i][j]

= 第

i

天结束、持股

j

股的最优收益。四类转移：① 凭空建仓（此前

W

天没交易）

f[i][j]=-j\cdot ap_i

；② 不动

f[i][j]=f[i-1][j]

； ③ 买入

f[i][j]=\max_{\,j-as_i\le k<j}\big(f[i-W-1][k]-(j-k)ap_i\big)

；④ 卖出

f[i][j]=\max_{\,j<k\le j+bs_i}\big(f[i-W-1][k]+(k-j)bp_i\big)

。

为什么选它 · 优化关键

冷却把「合法转移源」精确锁到

i-W-1

那一天，是状态机「隔

W

天才能再动」的硬核版。③④ 的内层

\max

是定长滑动窗口取极值——把式子按

k

拆成「只含

k

的项 + 只含

j

的项」后，用单调队列把每天的转移从

O(\max P^2)

降到

O(\max P)

，总复杂度

O(T\cdot\max P)

。它示范了状态机 DP 与单调队列优化的经典合流。

练习

P1799数列选 / 删两状态：设 f[i][j] = 前 i 个数里保留 j 个、且第 i 个保留时的最大「匹配数」（a_i 恰好落在第 j 位，即 a_i=j 记一分）。删则继承、留则从 f[i-1][j-1] 转来——正是「选 / 不选」状态机换了个计分规则。在洛谷打开

P1103书本整理保留 n−k 本的选段 DP：按高度排序后，设 f[i][j] = 前 i 本选 j 本、且第 i 本入选时的最小「宽度差之和」。第 i 本选或不选构成两状态，选时差值只与上一本入选者相邻——又一个线性状态机。在洛谷打开

P1868饥饿的奶牛区间不相交选取（打家劫舍的区间版）：把每段区间按右端点排序，f[x] = 覆盖到坐标 x 的最大收益。对每段 [l,r]，f[r]=max(f[r-1], f[l-1]+长度)——「选这段」要求前一段在 l 之前结束，正是相邻互斥推广到区间。在洛谷打开