数位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;}
}

二、题单

持续更新中~

• 233. 数字 1 的个数
• 2376. 统计特殊整数
• 1012. 至少有 1 位重复的数字
• 2719. 统计整数数目
  …