数位DP

看博客：https://leopoldacc.github.io/Blogs/2020/12/15/数位dp/

数位DP,记忆化搜索模板：

0x3f的模板，觉得挺好用的

string s = to_string(n);
int m = s.size();
int cache[m][1 << 10];
memset(cache, -1, sizeof(cache)); 
function<int(int, int, bool, bool)> f = [&](int i, int mask, bool is_limit, bool is_num) -> int {
    // boundary
    if (i == m) {
        return is_num; // is_num 为 true 表示得到了一个合法数字
    }
    // cache
    if (!is_limit && is_num && cache[i][mask] != -1) {
        return cache[i][mask];
    }

    int res = 0;
    if (!is_num) {
        res = f(i + 1, mask, false, false);
    }
    int low = is_num ? 0 : 1;
    int up = is_limit ? s[i] - '0' : 9;
    for (int d = low; d <= up; ++d) {
        if ((mask >> d & 1) == 0) {
            res += f(i + 1, mask | (1 << d), is_limit && d == up, true);
        }
    }
    if (!is_limit && is_num) {
        cache[i][mask] = res;
    }

    return res;
};


return n - f(0, 0, true, false);

https://leetcode.cn/problems/numbers-with-repeated-digits