[动态规划] 数位DP

数位DP

数位dp的题目一般会问，某个区间内，满足某种性质的数的个数。

对应的数位dp问题有相应的解题技巧：

1. 利用前缀和求某个区间内满足条件的数的个数
2. 利用树的结构来考虑（按位分类讨论）

度的数量

原题链接

思路

通过前缀和思想计算出从 0 ~ n的所有方案数，给定区间做差即可

将n分解为B进制数，从高位开始依次考虑每个数。

按照树形结构划分n，左分支为 0~a-1, 右分支为 a

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 40;

int K, B;
int f[N][N];

void init() {
    for (int i = 0; i < N; i ++)
        for (int j = 0; j <= i; j ++)
            if (!j) f[i][j] = 1;
            else f[i][j] = f[i-1][j] + f[i-1][j-1];

}

int dp(int n) { // 从 0 ~ n 符合条件的数的个数
    if (!n) return 0;

    vector<int>nums;
    while(n) {
        nums.push_back(n % B);
        n /= B;
    }
    // for (int i = 0; i < nums.size(); i ++) cout << nums[i] << ' ';
    // puts("");
    int res = 0, last = 0;
    for (int i = nums.size()-1; i >= 0; i --) {
        int x = nums[i]; // x = 0, x = 1, x > 1
        // 对x分类讨论
        // cout << "x : " << x << endl;
        if (x) { // x != 0 即 x > 0
            res += f[i][K-last]; // 该位填0, 剩下从i位中选择K-last个位置填1
            // cout << res << endl;
            // cout << i << ' ' << K-last << endl;
            // cout << f[i][K-last] << endl;
            if (x > 1) { // 该位可以填1
                if (K - last - 1 >= 0)
                    res += f[i][K-last-1]; // 剩下从i位中选择K-last-1个位置填1
                // 对于符合条件的已经处理完成，直接break
                break;
            } else {
                // 对应 x == 1
                last ++; // 该位置填 1
                if (last > K) break;
            }
        }

        // 最后一个分支，即最后一位，如果为1则已经被上方处理过，如果为0，则方案数加1
        if (i == 0 && last == K) res ++;
    }
    return res;
}
inline int read(){
    int num = 0;
    char c;
    bool flag = false;
    while ((c = getchar()) == ' ' || c == '\n' || c == '\r');
    if (c == '-') flag = true;
    else num = c - '0';
    while (isdigit(c = getchar()))
    num = num * 10 + c - '0';
    return (flag ? -1 : 1) * num;
}
int main() {
    init();
    int x = read(), y =read();
    K = read(), B = read();
    printf("%d\n", dp(y) - dp(x-1));
    return 0;
}

数字游戏

原题链接

思路

状态表示

f[i][j] 表示共有i位，最高位为j的个数

状态计算

f[i][j] = f[i-1][k] (k = j, j+1, j+2, j+3, ... 9)

C++ 代码

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

const int N = 40;

int f[N][N];

void init() {
    for (int i = 0; i < 10; i ++) f[1][i] = 1;
    for (int i = 2; i < N; i ++)
        for (int j = 0; j <= 9; j ++)
            for (int k = j; k < N; k ++)
                f[i][j] += f[i-1][k];
}

int dp(int n) {
    if (!n) return 1;
    vector<int> nums;
    while(n) nums.push_back(n%10), n/=10;

    int res = 0, last = 0; // last表示上一位的数字
    for (int i = nums.size() - 1; i >= 0; i --) {
        int x = nums[i];
        // 分支一：考虑从last~x-1
        for (int j = last; j < x; j ++) {
            res += f[i+1][j];
        }
		// 不满足条件后退出
        if (x < last) break;
        // 分支二：x分支
        last = x;
        if (!i) res ++;
    }
    return res;
}

int main() {

    init();
    int a, b;
    while(cin >> a >> b) cout << dp(b) - dp(a - 1) << endl;
    return 0;

}

Windy数

原题链接

思路

状态表示

f[i][j] 表示考虑前i位，最高位为j 的所有方案数量

状态计算

f[i][j] += f[i-1][k] (k = 0, 1, ..., 9)
abs(j-k) >= 2

前导0问题

枚举的第 i+1 位是最高位，不能填0。如果填0，那么答案就会加上f[i+1][0]举这样一个例子，
对于数字13，是满足windy数定义的，那么加上前导0之后的 013 就不会被 f[3][0] 加进去，原因就是abs(0-1)<2，这样就导致答案漏掉

因此分两部分来计算答案

• 第一部分考虑长度与 n 等长的数

  for (int i = len-1; i >= 0; i --)
      {
          int x = nums[i];
          for (int j = (i == len-1); j < x; j ++) {
              if (abs(last - j) >= 2) {
                  res += f[i+1][j];
              }
          }
  
          if (abs(last-x) < 2) break;
          else last = x;
          if (!i) res ++;
      }
  

• 第二部分考虑长度小于 n 的数

  for (int i = 1; i < len; i ++)
          for (int j = 1; j <= 9; j ++)
              res += f[i][j];
  

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>

using namespace std;

const int N = 11;

int f[N][N];

void init() {
    for (int i = 0; i < 10; i ++) f[1][i] = 1;
    for (int i = 2; i < N; i ++)
        for (int j = 0; j < 10; j ++)
            for (int k = 0; k < 10; k ++)
                if (abs(j-k) >= 2) f[i][j] += f[i-1][k];
}

int dp(int n) {
    if(!n) return 0;

    vector<int> nums;

    while(n) nums.push_back(n%10), n/=10;

    int res = 0;
    int last = -1000;
    int len = nums.size();
    for (int i = len-1; i >= 0; i --)
    {
        int x = nums[i];
        for (int j = (i == len-1); j < x; j ++) {
            if (abs(last - j) >= 2) {
                res += f[i+1][j];
            }
        }

        if (abs(last-x) < 2) break;
        else last = x;
        if (!i) res ++;
    }

    for (int i = 1; i < len; i ++)
        for (int j = 1; j <= 9; j ++)
            res += f[i][j];

    return res;
}

int main() {
    init();
    int a, b;
    cin >> a >> b;
    cout << dp(b) - dp(a-1) << endl;
    return 0;
}

数字游戏 II

原题链接

思路

状态转移

f[i][j][k] 表示考虑i位数，最高位为j，k所有位数之和模N后的余数 所有方案数

状态计算

f[i][j][k] += f[i-1][x][mod(k-j, P)] 前i-1位和模P的余数为mod(k-j, P)

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 40, M = 110;

int f[N][10][M];
int P;

int mod(int x, int y) {
    return (x % y + y) % y; // 将得到的负余数转化为0~y-1之间
}

void init() {
    memset(f, 0, sizeof f);
    for (int i = 0; i < 10; i ++) f[1][i][i%P] = 1;

    for (int i = 2; i < N; i ++) //位数
        for (int j = 0; j < 10; j ++) // 最高位
            for (int k = 0; k < P; k ++) // 所有位上的和
                for (int x = 0; x < 10; x ++) // 下一位
                    f[i][j][k] += f[i-1][x][mod(k-j, P)];

}

int dp(int n) {
    if (!n) return 1;

    vector<int> nums;

    while(n) nums.push_back(n%10), n/=10;

    int res = 0;
    int last = 0;
    for (int i = nums.size() - 1; i >= 0; i --) {
        int x = nums[i];
        for (int j = 0; j < x; j ++)
            res += f[i+1][j][mod(-last, P)]; // 前面位之和为 last, 后面数字的和加上last % N 应为0

        last += x;
        if (!i && last % P == 0) res ++;
    }

    return res;
}

int main() {
    int a, b;
    while(cin >> a >> b >> P) {
        init();
        cout << dp(b) - dp(a-1) << endl;
    }
    return 0;
}

不要62

原题链接

思路

状态表示

f[i][j] 表示考虑前i位, 最高位为j的方案数

状态转移

f[i][j] = f[i-1][k]
j != 6 && k != 2
j != 4
k != 4

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 11;

int f[N][10];

inline int read(){
    int num = 0;
    char c;
    bool flag = false;
    while ((c = getchar()) == ' ' || c == '\n' || c == '\r');
    if (c == '-') flag = true;
    else num = c - '0';
    while (isdigit(c = getchar()))
    num = num * 10 + c - '0';
    return (flag ? -1 : 1) * num;
}

void init() {
    for (int i = 0; i < 10; i ++)
        if (i != 4) f[1][i] = 1;
    for (int i = 2; i < N; i ++)
        for (int j = 0; j < 10; j ++)
        {
            if (j == 4) continue;
            for (int k = 0; k < 10; k ++)
                if (k == 4 || j == 6 && k == 2) continue;
                else f[i][j] += f[i-1][k];
        }
}

int dp(int n) {
    if (!n) return 1;
    vector<int> nums;
    while(n) nums.push_back(n%10), n /= 10;
    int res = 0, last = 0;
    for (int i = nums.size()-1; i >= 0; i --) {
        int x = nums[i];
        for (int j = 0; j < x; j ++) {
            if (j == 4 || last == 6 && j == 2) continue;
            else res += f[i+1][j];
        }

        if (x == 4 || last == 6 && x == 2) break;
        last = x;
        if (!i) res ++;
    }
    return res;
}

int main() {
    init();
    int n, m;
    while(n = read(), m = read(), n || m) {
        printf("%d\n", dp(m) - dp(n-1));
    }
    return 0;
}