数位DP模板总结

(Updated: )
(3 mins to read)

几个细节：

  • 只有当lim和zero都为0时才执行记忆化，因为只有这时状态才不依赖于当前的数字；否则对于每个数字都得memset一次
  • 从高位向低位dp，并且高位应该相应的存在数组的高位上，这样才能正确记忆化; 比如123应该转成s="321"
  • zero这个标志位有时候是不需要的，有时候可以稍微思考下可不可以去掉，当然加着也不会错
1
2
3
4
5
6
7
8
9
10
11
12
13
int DP(int d, bool lim, bool zero) {
    if (d == -1) return 1;
    auto &v = dp[d];
    if(!lim && !zero && v != -1) return v;
    int ans = 0, up = (lim ? s[d] - '0' : 9);
    for(int i = 0; i<=up; i++) Add(ans, DP(d - 1, lim && i==up, zero && i==0));
    if(!lim && !zero) v = ans;
    return ans;
}
int get(const char *s, int n) {
    reverse(s, s + n);
    return DP(n - 1, 1, 1);
}

很多时候是有上下限要求的，[low, high]，一种方式是get(high) - get(low - 1)（缺点是如果数字很大，以字符串形式给出，那还得手写一个大数减法，虽然也不难），另一种是直接一次dp，写起来也很简单，把标志位lim改成lim_l和lim_r就可以了。

1
2
3
4
5
6
7
8
9
int DP(int d, bool lim_l, bool lim_r, bool zero) {
    if (d == -1) return 1;
    auto &v = dp[d];
    if(!lim_l && !lim_r && !zero && v != -1) return v;
    int ans = 0, dn = (lim_l ? s[d] - '0' : 0), up = (lim_r ? s[d] - '0' : 9);
    for(int i = dn; i<=up; i++) Add(ans, DP(d - 1, lim_l && i==dn, lim_r && i==up, zero && i==0));
    if(!lim_l && !lim_r && !zero) v = ans;
    return ans;
}