Day 6 讲义：线性 DP、游戏 DP 与数位 DP 入口

动态规划不是背转移式。它是在把一个大问题拆成小问题时，记录已经算过的小问题答案。

今天所有 DP 题都先回答四个问题：

1. dp 状态表示什么？
2. 当前状态从哪些更小状态转移？
3. 初值是什么？
4. 按什么顺序计算，最后答案在哪里？

1. 线性 DP：沿着数组推进

线性 DP 的下标通常就是“处理到第几个元素”。状态必须足够描述未来决策需要的历史信息。

1.1 698A：最后一天做了什么

每天可以休息、比赛或健身，但同一种活动不能连续两天。

定义：

dp[i][0]：前 i 天中，第 i 天休息的最少休息天数
dp[i][1]：前 i 天中，第 i 天比赛的最少休息天数
dp[i][2]：前 i 天中，第 i 天健身的最少休息天数

第 i 天休息，昨天可以是任何状态：

dp[i][0] = min(dp[i-1][0], dp[i-1][1], dp[i-1][2]) + 1

若今天能比赛，昨天不能比赛：

dp[i][1] = min(dp[i-1][0], dp[i-1][2])

若今天能健身，昨天不能健身：

dp[i][2] = min(dp[i-1][0], dp[i-1][1])

1.2 参考代码

#include<bits/stdc++.h>
using namespace std;

const int INF = 1e9;
int dp[110][3];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    for(int j = 0; j < 3; j++) dp[0][j] = 0;

    for(int i = 1; i <= n; i++){
        int x;
        cin >> x;
        dp[i][0] = min({dp[i-1][0], dp[i-1][1], dp[i-1][2]}) + 1;
        dp[i][1] = dp[i][2] = INF;
        if(x == 1 || x == 3) dp[i][1] = min(dp[i-1][0], dp[i-1][2]);
        if(x == 2 || x == 3) dp[i][2] = min(dp[i-1][0], dp[i-1][1]);
    }

    cout << min({dp[n][0], dp[n][1], dp[n][2]}) << '\n';
    return 0;
}

核心不是三种活动，而是：未来只关心昨天选了哪一类。

2. 构造题也能有 DP 思维

489C 要构造长度为 m、数位和为 s 的最小与最大数。

每一位都可以问：

我放这个数字后，剩余位数能否凑出剩余数位和？

最大数：从左到右尽量放大，只要剩余和能放进剩余位。

最小数：从左到右尽量放小，但首位不能为 0。也可以先构造最大数，再反向处理；无论哪种方式，都要检查：

0 <= 剩余和 <= 9 × 剩余位数

这其实是“可行性 DP/贪心构造”：每一步保留一个仍可完成的后缀。

3. 后缀 DP：从当前位置开始做最优选择

1881E 中，位置 i 可以删除当前元素，或按规则保留一段。定义：

dp[i] = 从位置 i 开始处理到结尾，最少删除多少元素。

从后向前计算，因为转移会访问 dp[i+1] 或 dp[i+a[i]+1]。

典型两种选择：

删除当前位置：1 + dp[i+1]
保留一段：dp[i+a[i]+1]（前提是不越界）

这类题的关键是把“当前做什么”写成清楚的选择，而不是急着写循环。

4. 一次 DP 求多个量：766C

字符串分段时，一段是否合法由该段中每个字符允许的最大长度决定。

令：

ways[i] = 前 i 个字符的分段方案数

枚举最后一段的起点 j，从 i 向左扩展时维护：

limit = 这一段中所有字符允许长度的最小值

若段长 i-j+1 <= limit，这段合法：

ways[i] += ways[j-1]

同一轮枚举还能顺便更新：

最长合法段长度；
最少分段数。

启发：一个双重循环如果已经枚举了所有合法区间，常常可以同时维护多个答案。

5. 游戏 DP：当前位置是必胜还是必败

1033C 中，两人轮流移动。定义：

win[i] = 轮到当前玩家站在 i 时，是否存在必胜策略。

判定非常直接：

如果能走到一个对手必败的位置，当前必胜；
如果所有合法下一步都让对手必胜，当前必败。

win[i] = false;
for(每个合法下一步 j){
    if(!win[j]) win[i] = true;
}

计算顺序必须保证 win[j] 已知。本题按排列值从大到小处理，因为只能跳到值更大的位置。

游戏 DP 的一句话：

能把对手送进必败态，就是必胜态。

6. 数位 DP：给数字加上“前缀状态”

1036C 问区间内非零数位不超过 3 的数有多少。

先会写函数：

F(x) = [0,x] 中满足条件的数的数量

最终答案：

F(r) - F(l-1)

数位 DP 状态通常包含：

pos：处理到第几位；
cnt：已经用了几个非零位；
tight：前缀是否仍与 x 完全相同。

若 tight=1，当前位不能超过 x 对应位；若已经小于上界，当前位可取 0..9。

递归含义：

dfs(pos, cnt, tight)

表示从当前位继续填，最终能得到多少种合法后缀。

数位 DP 的重点不是模板，而是理解 tight：它保证你不会数到比 x 大的数。

7. DP 常见错误

8. 今日训练顺序

698A -> 489C -> 1881E -> 766C -> 1033C -> 1036C。

每题先写一句：

dp[i] / dp[i][state] 到底表示什么？

若这句话写不出来，先不要写转移。

9. 今日口诀

DP 先定状态义，初值转移顺序齐。
线性问题看昨天，后缀问题从后推。
能到必败就是赢，数位上界靠 tight。