动态规划(Dynamic Programming)本质上是图论问题。

数位 DP

按照数字的位数划分转移阶段
转移方式:枚举下一位数字填什么
限制条件:数位的上下界要求

  • [1, r] 区间数字个数
  • [l, r] 区间数字个数
  • [1, r] 区间最大值

树形 DP

按照树从根往下或者叶子网上划分阶段
转移方式:集合叶子或者父亲的信息
限制条件:不详

  • 给定一棵 N 个点的树,求有多少点
  • 给定一棵 N 个点的树,求最大点权值
  • 给定一棵 N 个点的树,求树的直径

状压 DP

枚举子集并把所有子集合并

//4^n
for (int a = 1; a < (1 << n); a++)
    for (int b = 1; b < a; b++)
        if ((a | b) == a) f[a] = merge(f[b], f[a ^ b]);
        // (a | b) == a 判断 b 是否为 a 的子集

上面的代码复杂度为 $O(4^n)$,建议使用下面的

//3^n
for (int a = 1; a < (1 << n); a++)
    for (int b = a; b; b = (b - 1) & a)
        f[a] = merge(f[b], f[a ^ b]);

枚举最后一个加进来的数再合并

for (int a = 1; a < (1 << n); a++)
    for (int b = 1; b <= n; b++)
        if (a & (1 << (b - 1))) work(a, b);
        // f[a ^ (1 << (b - 1))] => f[a]

博弈论 DP

必胜态和必败态

必胜态:存在一个操作能使当前状态转移到必败态。
必败态:所有终止的状态都是必败态,或者该状态上的所有操作都会转移到必胜态。​(不能一步走到必胜态​)

SG 函数

如果游戏状态转移构成一个 DAG​

  • SG(x) 为不在后继结点数值集合中的最小非负整数​
  • 终止态的 SG 函数值为 0​
  • 必胜态的 SG 函数值大于 0​
  • 必败态的 SG 函数值等于 0

复合游戏的和

SG 定理:复合游戏的 SG 函数值等于子游戏的 SG 函数值的异或和

// Nim Game 求 SG 值
sg[0] = 0;
for (int a = 1; a <= n; a++) {
    int cnt = 0;
    for (int b = 1; b <= a; b++)
        z[++cnt] = sg[a - b];
    sort(z + 1, z + cnt + 1);
    for (int b = 0, c = 1; ; b++)
        if (z[c] == b)
            while (z[c] == b) c++;
        else {
            sg[a] = b;
            break;
        }
}