(数位dp) 力扣数位dp 题集记录

天赐细莲

4544

2022.10.11

2024.01.19

发布于未知归属地

状态压缩 C++kmp 数位DP 状态机学习分享

前言
题单
END

前言

注意：本文不适合连一点数位dp概念的小白观看，且不会写过多文字作题解，一些尽在代码中

小白可以先把我上面那篇博客(至少第一题)学完了再来练习本文的题集

本文大都是以记忆化dfs的方式实现。

大多数题，靠着力扣的测评机制，在全局常驻提升了运行速度

🔖题目的特点

数位dp从题面上来看就是非常有特色的一类题

数据范围非常大(不能暴力)
和每个数位有关
有明显的数学风味
喜欢问范围[L, R]中有多少(不)符合的数
一般问的比较直白不会出阅读理解型的题

🔖碎碎念

力扣上的数位dp的题不多，还有好多是会员题

但数位dp的模板性很强，掌握好自己的模板后，就是考验状态转换的能力了，但是数位dp的状态转换一般都在题面直白的说明了

这点和线段树很像，模板很简单统一，但是状态记录和转换才是难点

有些互逆的题，如果会了一道，能顺便靠总量 - 互逆来ac。但是还是要靠自己来正向推到一下，会发现有很多不同。

若不确定道理是记录什么状态，有一个方法就是可以无脑记忆

如直接定义dp[bit][num][mask][state1][state2][state3]等等。因为数位dp的时间复杂度极低，因此一般不用担心超时或者超内存的情况

等ac后可以再考虑那几个维度是用不着的

对于前导零的处理是一个初学的大难点，需要仔细思考状态关系。一般来说最好有限特判走

当然可以根据一些题目的规律来，比如是判断特定字母的题，若与0无关，一般可以不用判断；但是若是模糊的范围性的题，则必须要考虑了

🔖题目关联表

题目	关系
357. 统计各位数字都不同的数字个数 2376. 统计特殊整数 1012. 至少有 1 位重复的数字	357,2376 1012互逆
233. 数字 1 的个数面试题 17.06. 2出现的次数	相同

题单

🏷️233. 数字 1 的个数

⭐经典数位dp弱化版

完全版：洛谷：P2602 (ZJOI2010) 数字计数

给定两个正整数 a 和 b，求在 [a,b] 中的所有整数中，每个数码(digit)各出现了多少次。

题意与思路

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

首先本题可以通过找规律来ac，但此法不是本文重点

这题最烦的其实是前导零的处理，但是力扣上的这题，是统计特定的非0数，因此即使不考虑前导零也能直接ac

下方代码可以ac上方洛谷的数字计数(完全版，考虑前导零)

Code

const int M = 10 + 12;
const int cmpNum = 1;

int dp[M][M];
int eachBit[M];
int __init__ = []() {
    memset(dp, -1, sizeof(dp));
    return 0;
}();

int dfs(int bit, int state, int isLimit, bool leadZero) {
    if (bit == 0) {
        return state;
    }
    if (!isLimit && !leadZero && dp[bit][state] != -1) {
        return dp[bit][state];
    }

    int ans = 0;
    int top = isLimit ? eachBit[bit] : 9;
    for (int cur = 0; cur <= top; cur += 1) {
        // 连着前导0的情况
        // 也要统计，不能continue
        // 只是不能提供多余贡献而已，本身也是情况
        if (leadZero && cur == 0) {
            ans += dfs(bit - 1, state, isLimit && cur == top, true);
        }
        // 数值相等贡献+1
        else if (cur == cmpNum) {
            ans += dfs(bit - 1, state + 1, isLimit && cur == top, false);
        }
        // 普通情况，正常获得子状态
        else {
            ans += dfs(bit - 1, state, isLimit && cur == top, false);
        }
    }

    if (!isLimit && !leadZero) {
        dp[bit][state] = ans;
    }
    return ans;
}

int digitDP(int n) {
    int len = 0;
    while (n) {
        eachBit[++len] = n % 10;
        n /= 10;
    }
    return dfs(len, 0, true, true);
}

class Solution {
public:
    int countDigitOne(int n) {
        return ::digitDP(n);
    }
};

🏷️357. 统计各位数字都不同的数字个数

⭐每个数字都不同

题意与思路

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

本题可以直接从排列组合的角度处理。每位从[0, 9] 中选取一位，下一位从剩余数字中再取一位

从数位dp的角度处理，因为要记录使用过的数字，因此就得状压一个mask来记录

注意特判前导零

第二维度的填数可以省略

由于本题只有9特殊样例，完全版请做该题2376. 统计特殊整数

互逆题：1012. 至少有 1 位重复的数字

Code

const int M = 10 + 10;

// 数位
// 填数
// mask状态记录
int dp[M][10][1024];
int eachBit[M];

// 初始化都为-1
int __init__ = []() {
    memset(dp, -1, sizeof(dp));
    return 0;
}();

// 数位
// 数字
// 状态记录
// 是否是上限
// 是否是前导零
int dfs(int bit, int pre, int mask, int isLimit, int leadZero) {
    if (bit == 0) {
        return 1;
    }
    if (!isLimit && !leadZero && dp[bit][pre][mask] != -1) {
        return dp[bit][pre][mask];
    }

    int ans = 0;
    int top = isLimit ? eachBit[bit] : 9;
    for (int cur = 0; cur <= top; cur += 1) {
        // 特判一连串的前导零
        if (leadZero && cur == 0) {
            ans += dfs(bit - 1, cur, 0, isLimit && cur == top, true);
        } else {
            int nex = mask | (1 << cur);
            // 未使用过，则搜索
            if (nex != mask) {
                ans += dfs(bit - 1, cur, nex, isLimit && cur == top, false);
            }
        }
    }

    if (!isLimit && !leadZero) {
        dp[bit][pre][mask] = ans;
    }
    return ans;
}

int digitDP(int n) {
    int len = 0;
    while (n) {
        eachBit[++len] = n % 10;
        n /= 10;
    } 
    return dfs(len, 0, 0, true, true);
}

class Solution {
public:
    int countNumbersWithUniqueDigits(int n) {
        n = pow(10, n);
        // 0 <= x < 10^n
        return ::digitDP(n - 1);
    }
};

🏷️600. 不含连续1的非负整数

⭐二进制数位dp

题意与思路

给定一个正整数 n ，返回范围在 [0, n] 都非负整数中，其二进制表示不包含 连续的 1 的个数。

通常数位dp是十进制的，而这题是二进制的，处理方式完全一样

核心的搜索限制是不包含连续的某个特定数

Code

记忆化dfs

递推

const int M = 32 + 10;

// 数位
// 填数
int dp[M][2];
int eachBit[M];

int __init__ = []() {
    memset(dp, -1, sizeof(dp));
    return 0;
}();

// bit 数位
// pre 前一位
// isLimit 是否是上限
int dfs(int bit, int pre, int isLimit) {
    if (bit == 0) {
        return 1;
    }
    if (!isLimit && dp[bit][pre] != -1) {
        return dp[bit][pre];
    }

    int ans = 0;
    // 注意二进制最大为1
    int top = isLimit ? eachBit[bit] : 1;
    for (int cur = 0; cur <= top; cur += 1) {
        if (pre == 1 && cur == 1) {
            continue;
        }
        ans += dfs(bit - 1, cur, isLimit && cur == top);
    }

    if (!isLimit) {
        dp[bit][pre] = ans;
    }
    return ans;
}

int digitDP(int n) {
    int len = 0;
    while (n) {
        eachBit[++len] = n % 2;
        n /= 2;
    }
    // 假设前一位是0，不影响本题
    return dfs(len, 0, true);
}

class Solution {
public:
    int findIntegers(int n) {
        return ::digitDP(n);
    }
};

🏷️788. 旋转数字

⭐有限状态机

题意与思路

将数字分为三类，无关类，正态类，错态类。统计无错态类有正态类的数量。

数位dp结合有限状态机的典型应用，需要好好理解和掌握。

Code

const int M = 10 + 10;

// 数位
// 有限状态机
int dp[M][3];
int eachBit[M];

// 初始化都为-1
int __init__ = []() {
    memset(dp, -1, sizeof(dp));
    return 0;
}();

// 有限状态机
// state 定义
// 0 未知态
// 1 错态
// 2 正确态
inline int check(int bit) {
    if (bit == 3 || bit == 4 || bit == 7) {
        return 1;
    }
    if (bit == 0 || bit == 1 || bit == 8) {
        return 0;
    }
    return 2;
}

// 数位
// 有限状态机
// 是否是上限
int dfs(int bit, int state, int isLimit) {
    if (bit == 0) {
        return state == 2;
    }
    if (!isLimit && dp[bit][state] != -1) {
        return dp[bit][state];
    }

    int ans = 0;
    int top = isLimit ? eachBit[bit] : 9;
    for (int cur = 0; cur <= top; cur += 1) {
        int nex = check(cur);

        // 错误态即使递归也永远无贡献
        if (nex == 1) {
            continue;
        }
        // 正确态
        else if (nex == 2) {
            ans += dfs(bit - 1, 2, isLimit && cur == top);
        }
        // 未知态，但是可能之前是正确的
        else {
            ans += dfs(bit - 1, state, isLimit && cur == top);
        }
    }

    if (!isLimit) {
        dp[bit][state] = ans;
    }
    return ans;
}

int digitDP(int n) {
    int len = 0;
    while (n) {
        eachBit[++len] = n % 10;
        n /= 10;
    } 
    return dfs(len, 0, true);
}

class Solution {
public:
    int rotatedDigits(int n) {
        return digitDP(n);
    }
};

🏷️902. 最大为 N 的数字组合

⭐给定数字组成的数

题意与思路

给定数字组成的数

注意前导零

本题一开始容易想到把每个使用的数字状态压缩，记录一个mask，作为一个dp的维度

但是根据题意，每个数字可以使用多次，因为这个mask实际表示的内容就比较模糊了

回归最初的只记录当前填写的数字是哪个，然后索搜后面那些合格

Code

class Solution {
private:
    // 数位dp标配
    static const int M = 10 + 10;
    int eachBit[M];
    // 数位
    // 填数
    int dp[M][10];

    // 回到本题
    // 记录哪个数字存在
    unordered_set<int> words;

    // bit 数位
    // pre 数字
    // 是否为上限
    // 是否为前导零
    int dfs(int bit, int pre, int isLimit, int leadZero) {
        // 因为递归的是所有合理情况，因此必然return 1
        if (bit == 0) {
            return 1;
        }
        if (!isLimit && !leadZero && dp[bit][pre] != -1) {
            return dp[bit][pre];
        }

        int ans = 0;
        int top = isLimit ? eachBit[bit] : 9;
        for (int cur = 0; cur <= top; cur += 1) {
            // 只递归可能存在值的情况
            if (cur == 0) {
                // 如果是前导零，则搜索
                if (leadZero) {
                    ans += dfs(bit - 1, cur, isLimit && cur == top,
                               cur == 0 && leadZero);
                }
                // 不是前导零，因为题意中没有0，必然不搜索
            } else {
                // 存在该数字
                if (words.find(cur) != words.end()) {
                    ans += dfs(bit - 1, cur, isLimit && cur == top,
                               cur == 0 && leadZero);
                }
                // 不存在则不搜索
            }
        }

        if (!isLimit && !leadZero) {
            dp[bit][pre] = ans;
        }
        return ans;
    }

    // 分割数字 [1, length]
    int digitDp(int n) {
        memset(dp, -1, sizeof(dp));
        int len = 0;
        while (n) {
            eachBit[++len] = n % 10;
            n /= 10;
        }
        return dfs(len, 0, true, true);
    }

public:
    int atMostNGivenDigitSet(vector<string>& digits, int n) {
        for (string& s : digits) {
            words.insert(stoi(s));
        }
        // 本题把0也计入，因此要减去
        return digitDp(n) - 1;
    }
};

🏷️1012. 至少有 1 位重复的数字

⭐状压 + 状态

题意与思路

给定正整数 n，返回在 [1, n] 范围内具有 至少 1 位 重复数字的正整数的个数。

和327题互逆

在处理到bit位时记录过当前这个mask再根据不同状态的记录

本题还有一种记录方法，但状态记录的太少，跑的很满。

此处若去掉state == 1不能ac，因为到state=0也return的话会损失很多可能转为state=1的情况

if (!isLimit && !leadZero && state == 1 && dp[bit][state] != -1) {return dp[bit][state];}

当不能ac时先不要慌，索性多加几维度状态，能加几个加几个，很有可能就ac了

Code

const int M = 10 + 10;

// 数位
// mask状压记录
// 正真的状态
int dp[M][1024][2];
int eachBit[M];

// 初始化都为-1
int __init__ = []() {
    memset(dp, -1, sizeof(dp));
    return 0;
}();

// 数位
// 状态记录
// mask状压
// 是否是上限
// 是否是前导零
int dfs(int bit, int state, int mask, int isLimit, int leadZero) {
    if (bit == 0) {
        return state == 1;
    }
    // 在处理到bit位时记录过当前这个mask再根据不同状态的记录
    if (!isLimit && !leadZero && dp[bit][mask][state] != -1) {
        return dp[bit][mask][state];
    }

    int ans = 0;
    int top = isLimit ? eachBit[bit] : 9;
    for (int cur = 0; cur <= top; cur += 1) {
        // 属于前导零状态
        if (leadZero && cur == 0) {
            ans += dfs(bit - 1, state, 0, isLimit && cur == top, true);
        } else {
            int nex = mask | (1 << cur);
            // 当前正好重复，或者本身就重复了
            if (nex == mask || state == 1) {
                ans += dfs(bit - 1, 1, nex, isLimit && cur == top, false);
            } else {
                ans += dfs(bit - 1, 0, nex, isLimit && cur == top, false);
            }
        }  
    }

    if (!isLimit && !leadZero) {
        dp[bit][mask][state] = ans;
    }
    return ans;
}

int digitDP(int n) {
    int len = 0;
    while (n) {
        eachBit[++len] = n % 10;
        n /= 10;
    } 
    return dfs(len, 0, 0, true, true);
}

class Solution {
public:
    int numDupDigitsAtMostN(int n) {
        return digitDP(n);
    }
};

🏷️1397. 找到所有好字符串

💀字符串数位dp + 有限状态机 (KMP)

题意与思路

给你两个长度为 n 的字符串 s1 和 s2 ，以及一个字符串 evil 。请你返回好字符串的数目。

好字符串的定义为：它的长度为 n ，字典序大于等于 s1 ，字典序小于等于 s2 ，且不包含 evil 为子字符串。

由于答案可能很大，请你返回答案对 10^9 + 7 取余的结果。

简单说就是在s1和s2之间，不包含evil的串数。

数位dp部分

这是一道字符串数位dp，解法和普通数值型一样。

注意：题意中是求[s1, s2]虽然也是用前缀和的方式处理

但是字符串不能像整数一样直接 dp[right] - dp[left - 1]

因此我们用dp[right] - dp[left] + 补差(left)的方式处理

kmp部分

这是一道有限状态机的题，不断在数位dp时，匹配evil的前缀

直到完全匹配完时，略去该状态

而当不匹配时，不是直接回到0，而是回退到尽可能匹配的状态，这就是著名的字符串算法kmp

每个人的kmp模板不太一样，用自己的就行

kmp模板题：28. 找出字符串中第一个匹配项的下标

Code

class Solution {
#define M 501
#define N 51

private:
    static const int mod = 1e9 + 7;

    vector<int> getNext(const string& s) {
        // 化下标为[1, n]
        string t = '*' + s;

        vector<int> next(t.size());
        next[1] = 0;  // next1必然为0
        // next数组偏移一步，从第二个字符开始判断
        for (int i = 2, j = 0; i < t.size(); i += 1) {
            while (j > 0 && t[i] != t[j + 1]) {
                j = next[j];
            }
            if (t[i] == t[j + 1]) {
                j += 1;
            }
            next[i] = j;
        }

        return next;
    }

private:
// state 有限状态机
// 0 一个字母都不匹配        正确态
// [1, len-1] 未完全 匹配   正确态
// len 完全匹配             错误态

    string cmp;  // [1, n]
    int cmpLen;
    vector<int> next;

    long long dp[M][N];
    string eachBit;

    /// @brief
    /// @param bit 数位
    /// @param state 有限状态机 匹配了第几个字符
    /// @param isLimit 上限
    /// @return
    int dfs(int bit, int state, int isLimit) {
        if (bit == 0) {
            return 1;
        }
        if (!isLimit && dp[bit][state] != -1LL) {
            return dp[bit][state];
        }

        long long ans = 0;
        char top = isLimit ? eachBit[bit] : 'z';
        for (char cur = 'a'; cur <= top; cur += 1) {
            // 下一个字母能匹配成功
            if (cur == cmp[state + 1]) {
                // 不是到结尾，则可以叠加
                if (state + 1 < cmpLen) {
                    ans += dfs(bit - 1, state + 1, isLimit && cur == top);
                }
            }
            // 匹配不成功，回退next
            else {
                int j = state;
                while (j > 0 && cur != cmp[j + 1]) {
                    j = next[j];
                }
                if (cur == cmp[j + 1]) {
                    j++;
                }
                ans += dfs(bit - 1, j, isLimit && cur == top);
            }

            ans %= mod;
        }

        if (!isLimit) {
            dp[bit][state] = ans;
        }
        return ans;
    }

    int digitDP(string s) {
        int len = s.size();
        reverse(s.begin(), s.end());
        eachBit = '*' + s;
        /// 起始匹配0个字符
        return dfs(len, 0, true);
    }

public:
    int findGoodStrings(int n, string s1, string s2, string evil) {
        memset(dp, -1, sizeof(dp));
        this->next = getNext(evil);
        this->cmpLen = evil.size();
        this->cmp = ' ' + evil;  // 化区间为[1, n]

        // (0, s2] - (0, s1] + 补差([s1]这个位置的状态抵消了，补上)
        long long ans =
            (digitDP(s2) - digitDP(s1) + (s1.find(evil) == string::npos)) % mod;
        return (ans + mod) % mod;
    }
};

🏷️2180. 统计各位数字之和为偶数的整数个数

⭐总体状态

题意与思路

给你一个正整数 num ，请你统计并返回小于或等于 num 且各位数字之和为偶数的正整数的数目。

正整数的各位数字之和是其所有位上的对应数字相加的结果。

整体状态进行状态的叠加

Code

const int M = 10 + 32;

int eachBit[M];
int dp[M][2];

int __init__ = []() {
    memset(dp, -1, sizeof(dp));
    return 0;
}();

int dfs(int bit, int status, bool islimit) {
    status = status & 1;
    if (bit == 0) {
        return status % 2 == 0;
    }
    if (!islimit && dp[bit][status] != -1) {
        return dp[bit][status];
    }

    int top = islimit ? eachBit[bit] : 9;
    int ans = 0;
    for (int cur = 0; cur <= top; cur += 1) {
        ans += dfs(bit - 1, status + cur, islimit && cur == top);
    }

    if (!islimit) {
        dp[bit][status] = ans;
    }
    return ans;
}

int digitDP(int num) {
    int len = 0;
    while (num) {
        eachBit[++ len] = num % 10;
        num /= 10;
    }
    return dfs(len, 0, true);
}

class Solution {
public:
    int countEven(int num) {
        // 数位dp中将0也算入了
        return ::digitDP(num) - 1;
    }
};

🏷️2376. 统计特殊整数

⭐357. 统计各位数字都不同的数字个数

题意与思路

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

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

完全一致：357. 统计各位数字都不同的数字个数

但是357的测试数据只有9个，可以用本题来检测357的代码正确性

互逆：1012. 至少有 1 位重复的数字

Code

const int M = 10 + 10;

int dp[M][10][1024];
int eachBit[M];

int __init__ = [] () {
    memset(dp, -1, sizeof(dp));
    return 0;
}();

int dfs(int bit, int pre, int mask, int isLimit, int leadZero) {
    if (bit == 0) {
        return 1;
    }
    if (!isLimit && !leadZero && dp[bit][pre][mask] != -1) {
        return dp[bit][pre][mask];
    }

    int ans = 0;
    int top = isLimit ? eachBit[bit] : 9;
    for (int cur = 0; cur <= top; cur += 1) {
        if (leadZero && cur == 0) {
            ans += dfs(bit - 1, cur, mask, isLimit && cur == top, true);
        } else {
            int nex = mask | (1 << cur);
            if (nex != mask) {
                ans += dfs(bit - 1, cur, nex, isLimit && cur == top, false);
            }
        }
    }

    if (!isLimit && !leadZero) {
        dp[bit][pre][mask] = ans;
    }
    return ans;
}

int digitDP(int n) {
    int len = 0;
    while (n) {
        eachBit[++len] = n % 10;
        n /= 10;
    }
    return dfs(len, 0, 0, true, true);
}

class Solution {
public:
    int countSpecialNumbers(int n) {
        // dfs中将0也算入
        return digitDP(n) - 1;
    }
};

🏷️2719. 统计整数数目

⭐字符串-1

题意与思路

弱化版：2180. 统计各位数字之和为偶数的整数个数

给你两个数字字符串 num1 和 num2 ，以及两个整数 max_sum 和 min_sum 。如果一个整数 x 满足以下条件，我们称它是一个好整数：

num1 <= x <= num2
min_sum <= digit_sum(x) <= max_sum.

请你返回好整数的数目。答案可能很大，请返回答案对 109 + 7 取余后的结果。

注意，digit_sum(x) 表示 x 各位数字之和。

看似有两个限制，实则分析一下：

num1 <= x <= num2
- 是统计的具体数值的要求
- 用差分处理
min_sum <= digit_sum(x) <= max_sum.
- 是具体数位dp的维护的状态
- 在数位dp中用state维护

此一分析，题目就非常了然了。同时应为定义digit_sum(x) 表示 x 各位数字之和。可见的这是一个维护总和的状态。

由于本文，受到min_sum <= digit_sum(x) <= max_sum的限制，不同测试样例间不属于共同规则，因此不能打表。

Code

constexpr int mod    = 1e9 + 7;
constexpr int M      = 22 + 10;
constexpr int MAXSUM = M * 9;

class Solution {
private:
    // dfs的限制
    int minSum, maxSum;
    // [1, len]
    int eachBit[M]; 
    int dp[M][MAXSUM];

    /**
     * bit      位数
     * state    状态，此处是每位的总和
     * isLimit  是否是上限
     */
    int dfs(int bit, int state, int isLimit) {
        // 先判是否到达上限
        if (state > maxSum) {
            return 0;
        }
        // 处理结尾了，记得判断是否满足下限
        if (bit == 0) {
            return state >= minSum;
        }

        // 记忆化
        if (!isLimit && dp[bit][state] != -1) {
            return dp[bit][state];
        }

        long long ans = 0;
        int top = isLimit ? eachBit[bit] : 9;
        for (int cur = 0; cur <= top; cur += 1) {
            ans += dfs(bit - 1, state + cur, isLimit && cur == top);
            ans %= mod;
        }

        if (!isLimit) {
            dp[bit][state] = ans;
        }

        return ans;
    }

    // 注意这里是把字符串映射到数组上
    int digitDP(const string &s) {
        int len = 0;
        for (int i = s.size() - 1; i >= 0; i += -1) {
            eachBit[++ len] = s[i] - '0';
        }
        return dfs(len, 0, true);
    }

public:
    int count(string num1, string num2, int min_sum, int max_sum) {
        memset(dp, -1, sizeof(dp));
        minSum = min_sum;
        maxSum = max_sum;

        long long ans = digitDP(num2) - digitDP(str_minus_one(num1));
        return (ans + mod) % mod;
    }

    // 将字符串数字-1
    string str_minus_one(string str) {
        int i = str.size() - 1;
        while (str[i] == '0') {
            i += -1;
        }
        // 最低的一个位-1
        str[i] += -1;
        // 回到可能收到影响的低位
        i += 1;
        for (; i < str.size(); i += 1) {
            str[i] = '9';
        }

        return str;
    }
};

🏷️面试题 17.06. 2出现的次数

⭐!0出现的次数

题意与思路

编写一个方法，计算从 0 到 n (含 n) 中数字 2 出现的次数。

和233. 数字 1 的个数完全一样。上面给出了处理前导零的情况

这里直接给出不考虑前导零的写法

为什么可以不考虑前导零

因为本题的限制是存在不为0的状态，0不会影响状态判断

Code

const int M = 10 + 10;

int dp[M][M];
int eachBit[M];

int __init__ = []() {
    memset(dp, -1, sizeof(dp));
    return 0;
}();

int dfs(int bit, int state, int isLimit) {
    if (bit == 0) {
        return state;
    }
    if (!isLimit && dp[bit][state] != -1) {
        return dp[bit][state];
    }

    int ans = 0;
    int top = isLimit ? eachBit[bit] : 9;
    for (int cur = 0; cur <= top; cur += 1) {
        // 指定特定值，可以不考虑前导零直接计算
        ans += dfs(bit - 1, state + (cur == 2), isLimit && cur == top);
    }

    if (!isLimit) {
        dp[bit][state] = ans;
    }
    return ans;
}

int digitDP(int n) {
    int len = 0;
    while (n) {
        eachBit[++len] = n % 10;
        n /= 10;
    }
    return dfs(len, 0, true);
}

class Solution {
public:
    int numberOf2sInRange(int n) {
        return ::digitDP(n);
    }
};

前言

🔖题目的特点

🔖碎碎念

🔖题目关联表

题单

⭐经典数位dp弱化版

题意与思路

Code

⭐每个数字都不同

题意与思路

Code

⭐二进制数位dp

题意与思路

Code

⭐有限状态机

题意与思路

Code

⭐给定数字组成的数

题意与思路

Code

⭐状压 + 状态

题意与思路

Code

💀字符串数位dp + 有限状态机 (KMP)

题意与思路

Code

⭐总体状态

题意与思路

Code

题意与思路

Code

⭐字符串-1

题意与思路

Code

⭐!0出现的次数

题意与思路

Code

END