算法动态规划

数位DP

字数统计: 6.3k字   |   阅读时长: 30分
, , ,

摘要: 数位 DP 的算法原理，题目列表以及题解

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

数位 DP 在基础的动态规划问题当中算是比较难的一类，因为数位 DP 的状态的物理意义不太好理解。其它的动态规划，比如区间 DP 状态的物理意义就是区间，状态压缩 DP 中状态的物理意义就是集合，这都比较好理解。

但是数位 DP 比其它 DP 好的一面是数位 DP 的思维相对比较固定。一个是解决的问题模式比较固定，一个是状态设计也比较固定，因此可以通过一些常见问题把数位 DP 的套路了解个大概。

$1 数位DP基本思想

数位 DP 主要解决的问题: 在一段区间 [L, R] 上的以下两类问题。

(1) 满足某些条件的数字个数

(2) 将 $x \in [L, R]$ 代到一个函数 f(x) 中, 一个数字 x 的 f(x) 值为一次贡献的量, 求总的贡献

时间复杂度一般是 $log_{10}L$。

数位 DP 的思考过程

以一个最简单的例子说明数位 DP 的思考过程: [L, R] 上的整数会共有多少个。

首先对于区间 [L, R] 上的问题, 首先变成解决前缀 [0, N] 的问题, [0, N] 上的问题解决后, 求一次 [0, R], 和 [0, L- 1] 就可以得到原问题的解了。

例如 N = 2357。

首先位数的范围是 3 ~ 0, 第 3 位为 2, 第 2 位为 3, 第 1 位为 5, 第 0 位为 7. 在枚举某个位可能的数字的时候, 必须要高位的数字已经确定了, 才能只当当前位的枚举范围。

比如当前为是第 2 位, 如果它的高位第 3 位是 0, 1, 则当前第 2 位的选择范围是 0 ~ 9 , 而当第 3 位为 2, 第 2 为的选择范围就变成 0 ~ 3。

分类：高位的数字可以分成两类, 如果没有顶到上界(例如第 3 位为 2), 则枚举范围就是 0 ~ 9, 即不限制, 而如果高位顶到了上界(例如第 3 位为 2), 当前位的范围就会被限制。

如果当前为枚举的数字因高位顶到了上界而被限制, 则当前位的数字枚举也要分类: 顶到上界, 未顶到上界, 这两种对低位的枚举影响不一样

如图：

  • 当高位未顶到上界(可能是未被限制, 也可能是被限制了但是选的数未顶到上界), 则低位的数字无限制, 可选 0 ~ 9。
  • 当高位顶到了上界, 则低位的数字被限制且要分类: 顶到上界和未顶到上界。

可以看出各个位上未被限制的情况被反复的复用, 这是用数位 DP 可以提高效率的地方。而顶到上界的情况, 只出现一次(图中下面那条链)。

DP 状态设计

dp[pos][lim] , pos 为当前的数位N-1 ~ 0, lim 表示是否顶到上界, 对于 -1 的地方

pos 到 -1 的时候可以 return 1, 使得个位的枚举有效.

DP 状态转移

1
2
3
dp[pos][lim]: 
dp[pos][0] = 10 * dp[pos - 1][0]
dp[pos][1] = digits[i] * dp[pos - 1][0] + dp[pos - 1][1]

因为顶到上界的时候只需要计算一次, 所有 lim 可以不放到 dp 数组里记忆化: 将 dp 数组改为 1 维, 但是在 dfs 的时候带着 lim 这个参数。

有的时候一串前导 0 需要特别处理。此时可以在 dfs 加一个状态 zero, 见后面的例题。

总结

  • 一般数位 DP 的状态必有的维度有 pos, lim
  • 前导零会对结果产生影响时, 加一维 zero
  • 可能需要带上前缀的某种状态 state, 此状态可能影响当前位的枚举, 也可能影响当前位枚举的值对答案的贡献

$2 数位DP题目

902. 最大为 N 的数字组合

给定一个按 非递减顺序 排列的数字数组 digits 。你可以用任意次数 digits[i] 来写的数字。例如，如果 digits = [‘1’,’3’,’5’]，我们可以写数字，如 ‘13’, ‘551’, 和 ‘1351315’。

返回 可以生成的小于或等于给定整数 n 的正整数的个数 。

提示：

1
2
3
4
5
6
1 <= digits.length <= 9
digits[i].length == 1
digits[i] 是从 '1' 到 '9' 的数
digits 中的所有值都 不同 
digits 按 非递减顺序 排列
1 <= n <= 1e9

示例 1：
输入：digits = [“1”,”3”,”5”,”7”], n = 100
输出：20
解释：
可写出的 20 个数字是：
1, 3, 5, 7, 11, 13, 15, 17, 31, 33, 35, 37, 51, 53, 55, 57, 71, 73, 75, 77.

示例 2：
输入：digits = [“1”,”4”,”9”], n = 1000000000
输出：29523
解释：
我们可以写 3 个一位数字，9 个两位数字，27 个三位数字，
81 个四位数字，243 个五位数字，729 个六位数字，
2187 个七位数字，6561 个八位数字和 19683 个九位数字。
总共，可以使用D中的数字写出 29523 个整数。

示例 3:
输入：digits = [“7”], n = 8
输出：1

算法：数位 DP

也是问 [1, N] 上的数字有多少个, 只是每一位只能用给定的数字, 因此在上面推导过程的基础上, 在转移的时候, 限制枚举的数字种类即可。

代码 (不带前导零状态)

1
2
3
num_set: 可选数字集合
digits[i]: 第 i 位的上界, 在第 i 位若被限制, 则需要取 digits[i]
getdp(...) : dfs

以下为不带前导零状态的数位DP模板。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution
{
public:
    int atMostNGivenDigitSet(vector<string>& D, int N)
    {
        set<int> num_set;
        for(const string &s: D)
            num_set.insert(s[0] - '0');

        vector<int> digits;
        while(N)
        {
            digits.push_back(N % 10);
            N /= 10;
        }

        vector<vector<int>> dp(digits.size(), vector<int>(2, -1));
        int n = digits.size();
        int ans = getdp(n - 1, 1, digits, num_set, dp);
        // 上面的计算只能算与 N 等长的数
        // 下面把更短的数字可能的贡献加上, 相当于有前导 0 
        for(int i = 1; i < n; ++i)
            ans += getdp(i - 1, 0, digits, num_set, dp);
        return ans;
    }

private:
    int getdp(int pos, int lim, const vector<int>& digits, const set<int>& num_set, vector<vector<int>>& dp)
    {
        if(pos == -1) return 1;
        if(dp[pos][lim] != -1)
            return dp[pos][lim];
        dp[pos][lim] = 0;
        int up = lim ? digits[pos] : 9; // 当前要枚举到的上界
        for(int i: num_set) // 枚举当前位所有可能数字
        {
            if(i > up)
                break;
            dp[pos][lim] += getdp(pos - 1, lim && i == up, digits, num_set, dp); // 本位被限制且选顶到上界的数字,下一位才被限制
        }
        return dp[pos][lim];
    }
};

代码 (带前导零状态)

增加 zero 状态, 表示高位是否是前导零。

  • 如果高位选了前导零, 则当前位无限制, 且还可以选前导零。
  • 如果高位没有选前导零且为顶到上界, 则当前位在可选数字集合的范围内无限制。
  • 如果高位顶到了上界, 则当前位的选择被限制。

以下为带前导零状态的数位DP模板。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution
{
public:
    int atMostNGivenDigitSet(vector<string>& D, int N)
    {
        set<int> num_set;
        for(const string &s: D)
            num_set.insert(s[0] - '0');

        vector<int> digits;
        while(N)
        {
            digits.push_back(N % 10);
            N /= 10;
        }

        vector<int> dp(digits.size(), -1);
        int n = digits.size();
        int ans = getdp(n - 1, 1, 1, digits, num_set, dp);
        return ans;
    }

private:
    int getdp(int pos, int lim, int zero, const vector<int>& digits, const set<int>& num_set, vector<int>& dp)
    {
        if(pos == -1) return !zero; // 如果是一直前导零直到 -1
        if(dp[pos] != -1 && !zero && !lim) // 关键: !zero 且 !lim 的时候, 才是复用的部分, 见图
            return dp[pos];
        int ans = 0;
        int up = lim ? digits[pos] : 9; // 当前要枚举到的上界
        if(zero)
            ans += getdp(pos -1, 0, 1, digits, num_set, dp);
        for(int i: num_set) // 枚举当前位所有可能数字
        {
            if(i > up)
                break;
            ans += getdp(pos - 1, lim && i == up, 0, digits, num_set, dp); // 本位被限制且选顶到上界的数字,下一位才被限制
        }
        if(!lim && !zero)
            dp[pos] = ans;
        return ans;
    }
};

357. 计算各个位数不同的数字个数

给你一个整数 n ，统计并返回各位数字都不同的数字 x 的个数，其中 0 <= x < 10n 。

提示：

1
0 <= n <= 8

示例 1：
输入：n = 2
输出：91
解释：答案应为除去 11、22、33、44、55、66、77、88、99 外，在 0 ≤ x < 100 范围内的所有数字。

示例 2：
输入：n = 0
输出：1

算法：数位 DP

数位DP的变化主要在前缀状态 state 上面。

1012 题中 state 的含义与本题相同

1
dp[pos][state] : 第 pos 位, 没有顶到上界, 不是前导零, 前缀的数字选择情况为 state 时, 的个数

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public:
    int countNumbersWithUniqueDigits(int n) {
        if(n == 0) return 1;
        vector<int> digits(n, 9);

        vector<vector<int>> dp(n, vector<int>((1 << 10) - 1, -1));
        int state = 0;
        int ans = getdp(n - 1, 1, 1, digits, state, dp);
        return ans;
    }

private:
    using ll = long long;

    int getdp(int pos, int lim, int zero, const vector<int>& digits, int& used, vector<vector<int>>& dp)
    {
        if(pos == -1) return 1; // 数字 0
        if(!lim && !zero && dp[pos][used] != -1)
            return dp[pos][used];

        int ans = 0;
        int up = lim ? digits[pos] : 9;
        if(zero)
            ans += getdp(pos - 1, 0, 1, digits, used, dp);
        for(int i = 0; i <= 9; ++i)
        {
            if(i > up) break;
            if(zero && i == 0) continue;
            if(used & (1 << i)) continue;
            used |= (1 << i);
            ans += getdp(pos - 1, lim && i == up, 0, digits, used, dp);
            used &= (~(1 << i));
        }
        if(!lim && !zero) dp[pos][used] = ans;
        return ans;
    }
};

233. 数字 1 的个数

给定一个整数 n，计算所有小于等于 n 的非负整数中数字 1 出现的个数。

提示：

1
0 <= n <= 1e9

示例 1：
输入：n = 13
输出：6

示例 2：
输入：n = 0
输出：0

算法：数位 DP

数位 DP 的第二类问题: 求贡献。

算贡献的时候带着一个 cnt, cnt 表示前缀中 1 的个数, 当前位选 1 则要将 cnt + 1。

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    int countDigitOne(int n) {
        if (n <= 0) return 0;
        vector<int> digits;
        while(n)
        {
            digits.push_back(n % 10);
            n /= 10;
        }
        int m = digits.size();
        vector<vector<vector<int>>> dp(m, vector<vector<int>>(m, vector<int>(2, -1)));
        return getdp(m - 1, 1, 0, digits, dp);
    }

private:
    int getdp(int pos, int lim, int cnt, const vector<int>& digits, vector<vector<vector<int>>>& dp)
    {
        if(pos == -1) return cnt;
        int &ans = dp[pos][cnt][lim];
        if(ans != -1) return ans;
        ans = 0;
        int up = lim ? digits[pos] : 9;
        for(int i = 0; i <= up; ++i)
        {
            ans += getdp(pos - 1, lim && (i == up), cnt + (i == 1), digits, dp);
        }
        return ans;
    }
};

1067. 范围内的数字计数

给定一个在 0 到 9 之间的整数 d，和两个正整数 low 和 high 分别作为上下界。返回 d 在 low 和 high 之间的整数中出现的次数，包括边界 low 和 high。

提示：

1
2
0 <= d <= 9
1 <= low <= high <= 2×10^8

示例 1：
输入：d = 1, low = 1, high = 13
输出：6
解释：
数字 d=1 在 1,10,11,12,13 中出现 6 次。注意 d=1 在数字 11 中出现两次。

示例 2：
输入：d = 3, low = 100, high = 250
输出：35
解释：
数字 d=3 在 103,113,123,130,131,…,238,239,243 出现 35 次。

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
public:
    int digitsCount(int d, int low, int high) {
        return solve(high, d) - solve(low - 1, d);
    }

private:
    int solve(int N, int d)
    {
        if(N == 0) return 0;
        vector<int> digits;
        while(N)
        {
            digits.push_back(N % 10);
            N /= 10;
        }
        int m = digits.size();
        vector<vector<int>> dp(m, vector<int>(m, -1)); // dp[pos][state]
        int ans = getdp(m - 1, 1, 1, digits, 0, dp, d);
        return ans;
    }

    int getdp(int pos, int lim, int zero, const vector<int>& digits, int state, vector<vector<int>>& dp, int d)
    {
        if(pos == -1) return state;
        if(!lim && !zero && dp[pos][state] != -1)
            return dp[pos][state];
        int ans = 0;
        if(zero)
            ans += getdp(pos - 1, 0, 1, digits, state, dp, d);
        int up = lim ? digits[pos] : 9;
        for(int i = 0; i <= 9; ++i)
        {
            if(i > up)
                break;
            if(zero && i == 0) continue;
            ans += getdp(pos - 1, lim && i == up, 0, digits, state + (i == d), dp, d);
        }
        if(!lim && !zero)
            dp[pos][state] = ans;
        return ans;
    }
};

248. 中心对称数 III

给定两个字符串 low 和 high 表示两个整数 low 和 high ，其中 low <= high ，返回 范围 [low, high] 内的 「中心对称数」总数 。

中心对称数 是一个数字在旋转了 180 度之后看起来依旧相同的数字（或者上下颠倒地看）。

示例 1:
输入: low = “50”, high = “100”
输出: 3

示例 2:
输入: low = “0”, high = “0”
输出: 1

提示:

1
2
3
4
1 <= low.length, high.length <= 15
low 和 high 只包含数字
low <= high
low and high 不包含任何前导零，除了零本身。

算法1：数位DP

本题是力扣中最难的哪一档了 。。。

1
dp[pos][lim]

有对称性的数位 DP, 在 pos 超过中间的时候需要特判, 若前一半没有顶到上界, 后半部分还可以随便选, 但前一半顶到上界了, 后半部分的数字取法就定死了, 没得选.

处理方法：例如 N = 35956, pos = 1 时, 高位选的数为 359，先看高位是 358 的时候, 合法的数有多少种, 然后再特判高位是 359 时, 后面要跟前面对称有没有存在的数。

奇数长和偶数长的问题需要特判。

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
class Solution {
public:
    int strobogrammaticInRange(string low, string high) {
        mapping[0] = 0;
        mapping[1] = 1;
        mapping[8] = 8;
        mapping[6] = 9;
        mapping[9] = 6;
        int result = solve(high) - solve(low) + check(high);
        if(result < 0)
            return 0;
        return result;
    }

private:
    unordered_map<int, int> mapping;

    int getdp(int pos, int lim, int odd, int fi, const vector<int>& digits, vector<vector<vector<int>>>& dp)
    {
        // fi 的意义与前导零类似
        if(pos == -1) return 1;
        int ans = dp[pos][lim][odd];
        if(!fi && ans != -1) return ans;
        ans = 0;
        int up = lim ? digits[pos] : 9;
        for(int i: {0, 1, 6, 8, 9})
        {
            if(i > up)
                break;
            if(fi && i == 0) // 都枚举严格等于长度的 , 最高位严格不是 0
                continue;
            if(odd && pos == 0 && (i == 6 || i == 9)) // 奇数长的中间位置只能是 0, 1, 8
                continue;
            ans += getdp(pos - 1, lim && i == up, odd, 0, digits, dp);
        }
        if(!fi)
            dp[pos][lim][odd] = ans;
        return ans;
    }

    int solve(const string& s)
    {
        if(s == "0") return 0;
        int n = s.size();
        vector<int> digits;
        for(int i = 0; i < (n + 1) / 2; ++i) // 仅枚举前一半
        {
            digits.push_back(s[i] - '0');
        }
        reverse(digits.begin(), digits.end());
        int m = digits.size();
        for(int i = 0; i < m; ++i)
        {
            if(digits[i] > 0)
            {
                --digits[i];
                break; // N = 35956 的例子中, 将前半部分变为 358
            }
            digits[i] = 9;
        }
        int ans = 0;
        vector<vector<vector<int>>> dp(m, vector<vector<int>>(2, vector<int>(2, -1)));
        if(digits.back() != 0) // 100000, 此时取一半, 前一半未顶上界时, 99 , 位数少了
            ans += getdp(m - 1, 1, n & 1, 1, digits, dp);
        for(int i = n - 1; i >= 1; --i) // 所有比当前串短的贡献都算一下
            ans += getdp((i + 1) / 2 - 1, 0, i & 1, 1, digits, dp);
        return ans + 1; // "0"
    }

    bool check(const string& s)
    {
        // 处理前缀都顶到上界的情况
        // 看后半部分对称过去之后是否合法
        int n = s.size();
        string ns;
        for(int i = 0; i < (n + 1) / 2; ++i)
        {
            if(!mapping.count(s[i] - '0'))
                return false;
        }
        if((n & 1) && (s[(n - 1) / 2] == '6' || s[(n - 1) / 2] == '9'))
            return false;
        for(int i = (n + 1) / 2; i < n; ++i)
        {
            int a = s[i] - '0';
            int b = mapping[s[n - i - 1] - '0'];
            if(a != b)
                return a > b; // 前面一半与限制一样，对称过去的部分只要比限制小就是能取到的
        }
        return true;
    }
};

算法2：回溯

以下是之前没学过数位 DP 时写过的 基于回溯的代码，还是数位 DP 的方法更好。

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
class Solution {
public:
    int strobogrammaticInRange(string low, string high) {
        int min_len = low.size(), max_len = high.size();
        int result = 0;
        string item;
        for(int len = min_len; len <= max_len; ++len)
        {
            int left = 0, right = len - 1;
            item.assign(len, '0');
            dfs(left, right, len, low, high, result, item);
        }
        return result;
    }

private:
    vector<char> chars = {'0','1','6','8','9'};
    vector<char> chars_reverse = {'0','1','9','8','6'};

    void dfs(int left, int right, int len, const string& low, const string& high, int& result, string& item)
    {
        int min_len = low.size(), max_len = high.size();

        if(left > right)
        {
            if((len > min_len || item >= low) && (len < max_len || item <= high))
            ++result;
            return;
        }

        if(left == right)
        {
            for(char ch: vector<char>{'0', '1', '8'})
            {
                item[left] = ch;
                if((len > min_len || item >= low) && (len < max_len || item <= high))
                    ++result;
                item[left] = '0';
            }
            return;
        }

        // left < right
        for(int i = 0; i < (int)chars.size(); ++i)
        {
            char ch = chars[i];
            if(left == 0 && ch == '0') continue;
            item[left] = ch;
            item[right] = chars_reverse[i];
            dfs(left + 1, right - 1, len, low, high, result, item);
            item[left] = '0';
            item[right] = '0';
        }
    }
};

1088. 易混淆数 II

易混淆数（Confusing Number）指的是一个数字在整体旋转 180° 以后，能够得到一个和原来 不同 的数，且 新数字的每一位都应该是有效的。

本题我们会将数字旋转 180° 来生成一个新的数字。

  • 当 0、1、6、8、9 旋转 180° 以后，我们得到的新数字分别为 0、1、9、8、6。
  • 当 2、3、4、5、7 旋转 180° 后，是 无法 得到任何数字的。

请注意，在旋转一个数字之后，我们可以忽略前导零。

  • 例如，在旋转 8000 之后，我们有 0008 ，它被认为只是 8 。

给出正整数 n，请你返回 [1, n] 范围内的 易混淆数 的数量 。

示例 1：
输入：n = 20
输出：6
解释：易混淆数为 [6,9,10,16,18,19]。
6 转换为 9
9 转换为 6
10 转换为 01 也就是 1
16 转换为 91
18 转换为 81
19 转换为 61

示例 2：
输入：n = 100
输出：19
解释：易混淆数为 [6,9,10,16,18,19,60,61,66,68,80,81,86,89,90,91,98,99,100]。

提示：

1
1 <= n <= 1e9

算法：数位 DP

上一题 248. 中心对称数 III 是找翻过来看起来一样的, 本题是找翻过来看起来不一样的. 因此可以先找出翻过来看起来一样的 A, 然后将所有可能的数的个数减去 A.

而所有可能的数的个数就是902. 最大为 N 的数字组合. 因此本题是两道题合并了一下.

代码 (D++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
class Solution {
public:
    int confusingNumberII(int N) {
        // lc248
        mapping[0] = 0;
        mapping[1] = 1;
        mapping[8] = 8;
        mapping[6] = 9;
        mapping[9] = 6;
        int positive_cnt = solve(to_string(N)) - 1 + check(to_string(N));
        positive_cnt = max(positive_cnt, 0);

        // lc902
        set<int> num_set({0, 1, 6, 8, 9});
        vector<int> digits;
        while(N)
        {
            digits.push_back(N % 10);
            N /= 10;
        }
        int m = digits.size();
        vector<int> dp(m, -1);
        int cnt = getcnt(m - 1, 1, 1, digits, dp, num_set);
        return cnt - positive_cnt;
    }
private:
    unordered_map<int, int> mapping;

    // lc902
    int getcnt(int pos, int lim, int zero, const vector<int>& digits, vector<int>& dp, const set<int>& num_set)
    {
        if(pos == -1) return !zero;
        if(!lim && !zero && dp[pos] != -1)
            return dp[pos];
        int ans = 0;
        if(zero)
            ans += getcnt(pos - 1, 0, 1, digits, dp, num_set);
        int up = lim ? digits[pos] : 9;
        for(int i: num_set)
        {
            if(i > up)
                break;
            if(zero && i == 0) continue;
            ans += getcnt(pos - 1, lim && i == up, 0, digits, dp, num_set);
        }
        if(!zero && !lim) dp[pos] = ans;
        return ans;
    }

    // lc 248
    int getdp(int pos, int lim, int odd, int fi, const vector<int>& digits, vector<vector<vector<int>>>& dp)
    {
        // fi 的意义与前导零类似
        if(pos == -1) return 1;
        int ans = dp[pos][lim][odd];
        if(!fi && ans != -1) return ans;
        ans = 0;
        int up = lim ? digits[pos] : 9;
        for(int i: {0, 1, 6, 8, 9})
        {
            if(i > up)
                break;
            if(fi && i == 0) // 都枚举严格等于长度的 , 最高位严格不是 0
                continue;
            if(odd && pos == 0 && (i == 6 || i == 9)) // 奇数长的中间位置只能是 0, 1, 8
                continue;
            ans += getdp(pos - 1, lim && i == up, odd, 0, digits, dp);
        }
        if(!fi)
            dp[pos][lim][odd] = ans;
        return ans;
    }

    int solve(const string& s)
    {
        if(s == "0") return 0;
        int n = s.size();
        vector<int> digits;
        for(int i = 0; i < (n + 1) / 2; ++i) // 仅枚举前一半
        {
            digits.push_back(s[i] - '0');
        }
        reverse(digits.begin(), digits.end());
        int m = digits.size();
        for(int i = 0; i < m; ++i)
        {
            if(digits[i] > 0)
            {
                --digits[i];
                break; // N = 35956 的例子中, 将前半部分变为 358
            }
            digits[i] = 9;
        }
        int ans = 0;
        vector<vector<vector<int>>> dp(m, vector<vector<int>>(2, vector<int>(2, -1)));
        if(digits.back() != 0) // 100000, 此时取一半, 前一半未顶上界时, 99 , 位数少了
            ans += getdp(m - 1, 1, n & 1, 1, digits, dp);
        for(int i = n - 1; i >= 1; --i) // 所有比当前串短的贡献都算一下
            ans += getdp((i + 1) / 2 - 1, 0, i & 1, 1, digits, dp);
        return ans + 1; // "0"
    }

    bool check(const string& s)
    {
        // 处理前缀都顶到上界的情况
        // 看后半部分对称过去之后是否合法
        int n = s.size();
        string ns;
        for(int i = 0; i < (n + 1) / 2; ++i)
        {
            if(!mapping.count(s[i] - '0'))
                return false;
        }
        if((n & 1) && (s[(n - 1) / 2] == '6' || s[(n - 1) / 2] == '9'))
            return false;
        for(int i = (n + 1) / 2; i < n; ++i)
        {
            int a = s[i] - '0';
            int b = mapping[s[n - i - 1] - '0'];
            if(a != b)
                return a > b; // 前面一半与限制一样，对称过去的部分只要比限制小就是能取到的
        }
        return true;
    }
};

788. 旋转数字

我们称一个数 X 为好数, 如果它的每位数字逐个地被旋转 180 度后，我们仍可以得到一个有效的，且和 X 不同的数。要求每位数字都要被旋转。

如果一个数的每位数字被旋转以后仍然还是一个数字， 则这个数是有效的。0, 1, 和 8 被旋转后仍然是它们自己；2 和 5 可以互相旋转成对方（在这种情况下，它们以不同的方向旋转，换句话说，2 和 5 互为镜像）；6 和 9 同理，除了这些以外其他的数字旋转以后都不再是有效的数字。

现在我们有一个正整数 N, 计算从 1 到 N 中有多少个数 X 是好数？

提示：

1
N 的取值范围是 [1, 10000]。

示例：
输入: 10
输出: 4
解释:
在[1, 10]中有四个好数： 2, 5, 6, 9。
注意 1 和 10 不是好数, 因为他们在旋转之后不变。

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {
public:
    int rotatedDigits(int N) {
        num_set = {2, 5, 6, 9};
        return solve(N);
    }

private:
    unordered_set<int> num_set;
    int solve(int n)
    {
        vector<int> digits;
        while(n)
        {
            digits.push_back(n % 10);
            n /= 10;
        }
        int m = digits.size();
        vector<vector<int>> dp(2, vector<int>(m, -1));
        int ans = getdp(m - 1, 1, 1, 0, digits, dp);
        return ans;
    }

    int getdp(int pos, int lim, int zero, int state, const vector<int>& digits, vector<vector<int>>& dp)
    {
        if(pos == -1) return state == 1;
        if(!zero && !lim && dp[state][pos] != -1)
            return dp[state][pos];
        int ans = 0;
        if(zero)
            ans = getdp(pos - 1, 0, 1, 0, digits, dp);
        int up = digits[pos];
        for(int i: {0, 1, 2, 5, 6, 8, 9})
        {
            if(lim && i > up) break;
            if(i == 0 && zero)
                continue;
            ans += getdp(pos - 1, lim && i == up, 0, state || num_set.count(i) > 0, digits, dp);
        }
        if(!zero && !lim)
            dp[state][pos] = ans;
        return ans;
    }
};

$3 数位 DP 其它题目

1.

$F(x) = A_{n}2^{n-1} + A_{n - 1}2^{n-2} + … + A_{1}2^{0}$, 给定Ａ, [L, R] 有多少数字 x 满足 $F(x) < F(A)$

1
2
3
4
5
dp[pos][lim]
sum 在 dfs 的过程中带着, 表示贡献
当前数字选 i: 产生 i* 2 ^ (pos - 1) 的贡献
将该贡献从 sum 中减去
当 sum < 0 的时候就到上界了

2.

求 [1, N] 中的数字个数, 要求至少出现一次 “49” 子串。

1
2
dp[pos][lim][f][pre]
pos, lim 为常规的数位 dp 的状态, f 表示 "49" 是否出现过, pre 表示高位是否为 4

可以逆向思维, 找不包含 49 的数字, 这样状态可以少一维。

1
2
dp[pos][lim][pre]
pos, lim 为常规的数位 dp 的状态, pre 表示高位是否为 4

3.

求 [L, R] 中的数字个数, 不可出现 “62” 子串, 且不能出现 “4”。

与上一题几乎一样, [L, R] 的处理: [0, L - 1], [0, R] 两个问题分别求一次。

4.

[L, R], 相邻数字差至少为 2。

1
dp[pos][lim][pre][zero]

5.

[L, R] 二进制表示中 0 的个数不少于 1 的个数。

在模板代码的十进制分解部分：

1
2
3
4
5
6
vector<int> digits;
while(N)
{
    digits.push_back(N % 10);
    N /= 10;
}

改成二进制分解：

1
2
3
4
5
6
vector<int> digits;
while(N)
{
    digits.push_back(N % 2);
    N /= 2;
}

在二进制的基础上，数位 DP 算法如下：

1
2
3
4
5
dp[pos][lim][cnt0][cnt1]
cnt0: 非前导 0 的 0 的个数
cnt1: 1 的个数
前导零的状态 zero 可以不加: 当 0 出现且是前导零的时候, cnt1 一定得是 0
pos = -1 时, 通过 cnt0 和 cnt 1 判断数字是否合法

6.

[L, R] 能被 x 整除, 且只能用给定数字。

1
2
dp[pos][lim][mod]
当 pos = -1, mod 为 0 是合法的
Share