首页 > 代码库 > 数位dp初步——数位dp的两种方式
数位dp初步——数位dp的两种方式
数位dp：一类统计区间[L,R]内某种符合规定的数字个数的题目。特征是R的范围会很大，O(N)范围内无法完成。
一般而言，解决这类题目有两种方式，一种是递推，另一种是记忆化搜索。
递推：
1）利用dp求出数组f[i][j]（表示有i位，最高位为j的数字中符合要求的数字的个数）
2）根据给出的[L,R]，利用f[]统计答案
记忆化搜索：
1 int dfs(int pos,int pre,int lim){//当前位置 前一位的数字 是否有限制 2 if(pos<=0)return 1; 3 if(pre>=0&&!lim&&f[pos][pre]!=-1)return f[pos][pre];//如果当前没有限制且此情况已搜索过，则返回 4 int rng=(lim?bit[pos]:9),ret=0;//确定范围 5 foru(i,0,rng) 6 if(check(...))//如果符合要求 递归下一位 7 ret+=dfs(pos-1,(pre<0&&i==0)?pre:i,lim&&(i==rng));//下一位 判断是否为第一位 是否有限制 8 if(pre>0&&!lim)f[pos][pre]=ret;//若无限制 记录 9 return ret;10 }
私以为，如果一道数位DP题同时支持两种写法，则记忆化搜索的编码难度和逻辑清晰度是优于递推的，递推的统计冗长还容易漏情况。
数位dp初步——数位dp的两种方式
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。