数位 DP 通用模板_哔哩哔哩_bilibili先来看这道问题2376. 统计特殊整数 - 力扣LeetCode如果n62345这里要求所有满足条件的情况可以一步一步从高位去试这里从最高位开始可以选择 0到6之间的数字注意一个细节如果一直选0最后一位选个合理的值是可取的因为从最高位开始一直选的0与其说是选择了0倒不如说是跳过了。0000110086第一种情况就是合理的第二种情况就是不合理的因此需要一个变量bool is_number去记录是否在一直跳过同时对于每次数字的选择也是需要考虑的如果说前面的数字选的都是n各个位的那么这一位的选择就要从考虑n在该位置上的情况了但是呢如果前面选择了小的就不用考虑了所以后面所有位都可以从0到9选择了这是后也需要一个变量来存储前置的位数与n的关系bool is_limit这里选择dfs从高到低选递归终止条件就是填完了每个位置之后再判断一下这些位置是不是都是0如果是就返回0否则就是一种正确情况返回一可以用前置零这个变量作为返回1还是0剩下的内容就是dfs排列组合了如果前面一直在跳0就要分类讨论了这一位也跳一起这一位不跳那就是从一开始的同时如果前面没有一直跳那可以从0开始选int ret0; if(!is_number){ retdfs(false,false,depth1); }对于选到多大可以看is_limit若果有限制那最高值就不是9了int i1-is_number; int cntis_limit ? num[depth] : 9; while(icnt){ if(has[i]){ i; continue; } has[i]1; if(cntiis_limit) retdfs(true,true,depth1); else{ retdfs(true,false,depth1); } has[i]0; i ; }整体代码class Solution { int has[11]; vectorint num;//用来存储n的每一位 int dfs(bool is_number,bool is_limit,int depth){ if(depthnum.size()) return is_number?1:0; int ret0; if(!is_number){ retdfs(false,false,depth1); } int i1-is_number; int cntis_limit ? num[depth] : 9; while(icnt){ if(has[i]){ i; continue; } has[i]1; if(cntiis_limit) retdfs(true,true,depth1); else{ retdfs(true,false,depth1); } has[i]0; i ; } return ret; } public: int countSpecialNumbers(int n) { int tempn; memset(has,0,sizeof(has)); while(temp){ num.push_back(temp%10); temptemp/10; } reverse(num.begin(),num.end()); int ansdfs(false,true,0); return ans; } };注意这里主函数调用dfs时要选false true因为更高位是跳过的同时是有限制条件的第二次跳就没有限制条件了至于dp就是加入记忆化搜索这是dfs的做法时间复杂度很高而灵神用的是python本身没有记忆化搜索。我用的是c这就很尴尬了。等正在学习如何实现记忆化搜索待更新吧。