数位DP万能模板-Toy模板网

这篇具有很好参考价值的文章主要介绍了数位DP万能模板。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

☆* o(≧▽≦)o *☆嗨~我是小奥🍹
📄📄📄个人博客：小奥的博客
📄📄📄CSDN：个人CSDN
📙📙📙Github：传送门
📅📅📅面经分享（牛客主页）：传送门
🍹文章作者技术和水平有限，如果文中出现错误，希望大家多多指正！
📜 如果觉得内容还不错，欢迎点赞收藏关注哟！ ❤️

一、数位DP模板

模板出处：两种数位 DP 模板，附题单（Python/Java/C++/Go）
作者：灵茶山艾府

class Solution {
    char[] s; // 表示限制n的字符形式
    int[][] cache; // 记忆化数组 


    // i    表示当前构造的下标
    // cnt 是一个根据题目需求的变量，比如
    //      (1)二进制字符串，如果某个数存在，那么该数对应的二进制数为1
    //         比如{0, 2, 3}，则mask为 1101
    //      (2)表示特殊数的个数
    // isLimit 表示前面填的数字是否都是n对应位上的（即是否受到n的约束），
    //      如果为true，那么至多为(int)s[i]
    //      如果为false，否则至多为9
    // isNum 表示前面是否填了数字（是否跳过，一般用于判断前导0是否有影响）：
    //      如果为true，那么当前位可以从0开始，
    //      如果为false，那么可以跳过，或者从1开始填数字
    public int dfs(int i, int cnt, boolean isLimit, boolean isNum) {
        if (i == s.length) {
            return cnt; // 返回结果 
        } 
        // 这里是记忆化搜索优化
        if (!isLimit && cache[i][mask] != -1) {
            return cache[i][mask];
        }
        int res = 0;
        // up表示上界，如果前面填的数字和n一样，则至多填 s[i]。否则至多填9。
        int up = isLimit ? s[i] - '0' : 9;
        // 枚举要填入的数字d，一般从0开始，有特殊情况也需要处理
        for(int d = 0; d <= up; d++) {
             res += dfs(i + 1, cnt的处理 , isLimit && d == up, true);
        }
        cache[i][mask] = res;
        return res;
    }
}