数位DP 模板

2376. 统计特殊整数 - 力扣（LeetCode）

2376. 统计特殊整数 - 如果一个正整数每一个数位都是 互不相同 的，我们称它是 特殊整数 。 给你一个 正 整数 n ，请你返回区间 [1, n] 之间特殊整数的数目。   示例 1： 输入：n = 20 输出：19 解释：1 到 20 之间所有整数除了 11 以外都是特殊整数。所以总共有 19 个特殊整数。 示例 2： 输入：n = 5 输出：5 解释：1 到 5 所有整数都是特殊整数。 示例 3： 输入：n = 135 输出：110 解释：从 1 到 135 总共有 110 个整数是特殊整数。 不特殊的部分数字为：22 ，114 和 131 。   提示： * 1 <= n <= 2 * 109

https://leetcode.cn/problems/count-special-integers/description/

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
const int inf = 2e9;
typedef long long ll;
class Solution {
public:
    int countSpecialNumbers(int n) {
        string s = to_string(n);
        int m = s.size();
        vector<vector<int>>dp(m,vector<int>(1<<10,-1));
        function<int(int, int, bool, bool)> f =
            [&](int i, int mask, bool is_num, bool is_limit) -> int {
            if (i == m) {
                return is_num;
            }
            if (!is_limit && is_num && dp[i][mask] != -1) {
                return dp[i][mask];
            }
            int res = 0;
            if (!is_num) {
                res = f(i + 1, mask, false, false);
            }
            int up = is_limit ? s[i] - '0' : 9;
            for (int d = 1 - is_num; d <= up; d++) {
                if ((mask & (1 << d)) == 0)
                    res += f(i + 1, mask | (1 << d), true, is_limit && d == up);
            }
            if (!is_limit && is_num) {
                dp[i][mask] = res;
            }
            return res;
        };
        return f(0, 0, false, true);
    }
};