数位dp模板总结

发表于 分类于

数位dp: 给定一个闭区间[0, n]，让你求这个区间中满足某种条件的数的总数。

计算[0, n]中数字2出现的次数

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:
    vector<int> nums;
    int dp[11][11];
    int numberOf2sInRange(int n) {
        while(n > 0) {
            nums.push_back(n % 10);
            n = n / 10;
        }
        reverse(nums.begin(), nums.end());
        memset(dp, -1, sizeof(dp));
        return f(0, true,0);
    }
    int f(int i, int is_limit, int ans) {
        if(i == nums.size())
            return ans;
        int res = 0;
        if(!is_limit && dp[i][ans] >= 0) return dp[i][ans];
        int down = 0, up = 9;
        if(is_limit) up = nums[i];
        for(int k = down; k <= up; k++){
            if(k == 2)
                res += f(i + 1, is_limit && k == up, ans + 1);
            else
                res += f(i + 1, is_limit && k == up, ans);
        }
        if(!is_limit) dp[i][ans] = res;
        return res;
    }
};

计算[0, n] 范围的非负整数中，有多少个整数的二进制表示中不存在 连续的 1

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
class Solution {
public:
    vector<int> nums;
    int dp[1010][2];
    int findIntegers(int n) {
        while(n > 0) {
            nums.push_back(n % 2);
            n /= 2;
        }
        reverse(nums.begin(), nums.end());
        memset(dp, -1, sizeof(dp));
        return f(0, false, true);
    }
    int f(int k, bool have_one, bool is_limit) {
        if(k == nums.size())
            return 1;
        int res = 0, down = 0, up = 1;
        if(is_limit) up = nums[k];
        if(!is_limit && dp[k][have_one] >= 0) return dp[k][have_one];
        for(int i = down; i <= up; i++) {
            if(have_one && i) break;
            res += f(k + 1, i, is_limit && i == up);
        }
        if(!is_limit) dp[k][have_one] = res;
        return res;
    }
};

最大为N的数字组合

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

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

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
class Solution {
public:
    vector<int> num;
    vector<int> numbers;
    vector<int> dp;
    int atMostNGivenDigitSet(vector<string>& digits, int x) {
        for(auto digit:digits) 
            numbers.push_back(stoi(digit));
        while(x > 0){
            num.push_back(x % 10);
            x = x / 10;
            dp.push_back(-1);
        }
        reverse(num.begin(), num.end());
        return f(0, true, false);
    }
    int f(int i, bool is_limit, bool is_number) {
        if(i == num.size())
            return is_number;
        if(!is_limit && is_number && dp[i] >= 0) return dp[i];
        int res = 0;
        if(!is_number)
            res = f(i + 1, false, false);
        int up = 9;
        if(is_limit) up = num[i];
        for(auto number: numbers) {
            if(number > up) break;
            res += f(i + 1, number == up && is_limit, true);
        }
        if (!is_limit && is_number) dp[i] = res; 
        return res;
    }
};

统计特殊整数

如果一个正整数每一个数位都是 互不相同 的，我们称它是 特殊整数 。

给你一个 正 整数 n ，请你返回区间 [1, n] 之间特殊整数的数目。

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
class Solution {
public:
    vector<int> num;
    int countSpecialNumbers(int n) {
        while(n > 0)
            num.push_back(n % 10), n /= 10;
        reverse(num.begin(), num.end());
        return f(0, 0, true, false);
    }

    int f(int i, int mask, bool is_limit, bool is_number) {
        if(i == num.size()) 
            return is_number;
        int res = 0;
        if(!is_number) 
            res += f(i + 1, mask, false, false);
        int down = 1, up = 9;
        if(is_limit) up = num[i];
        if(is_number) down = 0;
        for(int k = down; k <= up; k++) {
            if(!((mask >> k) & 1)) {
                res += f(i + 1, mask | (1 << k), is_limit && k == up, true);
            }
        }
        return res;
    }
};