核心内容摘要
厨房里的“战役”：一场关于味蕾与创意的美味博弈
信奥赛C提高组csp-s之数位DP详细讲解
基本概念数位DPDigit DP是一种用于解决数字位相关计数问题的动态规划方法常用于统计满足特定条件的数字个数。
典型应用场景包括统计区间内包含不含某些数字的数的个数统计满足特定位模式的数的数量计算数字位属性的统计值如数位和
核心思想数位拆分将数字转换为字符串或数组逐位处理状态压缩记录前导零、是否受限、前位状态等关键信息记忆化搜索通过DP数组缓存中间计算结果
状态设计要素pos当前处理的数位位置limit前面是否已经达到上限pre前一位数字的值lead前导零状态其他题目特定状态如数位和、特定标记等
经典案例1[洛谷P2602 数字计数]AC代码#includebits/stdc.husingnamespacestd;#definelllonglongints[15];//存储拆位的数字ll a,b;//取数字n的[l,r]之间的数:s数组逆序存数位llget(intl,intr){ll ans0;for(intil;ir;i--)ansans*10s[i];returnans;}//求10的次方llp(intn){ll ans1;while(n--)ans*10;returnans;}//求0到n中数字x出现的次数lldp(ll n,intx){if(n
return0;intk0;//k是数组s的下标while(n){s[k]n%10;n/10;}ll ans0;//计算x在每一位上的可能特殊情况如果x是0,要考虑0不能出现在最高位for(intik-!x;i1;i--){//逆序循环因为数组下标k存的n这个数的最高位//情况1前缀未取到up值的情况if(i!k)ans(get(k,i
-!x)*p(i-
;//情况2前缀取到up值的情况if(xs[i])ansget(i-1,
1;//
1: x等于当前位的数后面的只能取到最高位elseif(xs[i])ansp(i-
;//
2: x小于当前位的数后面的可以取满}returnans;}intmain(){cinab;for(inti0;i9;i){//枚举统计每个数码在区间a到b中出现的次数coutdp(b,i)-dp(a-1,i) ;//利用前缀和}return0;}代码功能该代码统计区间[a, b]内每个数字
出现的次数。
核心思想是逐位分析数字的每一位计算每个数字在每一位上的出现次数累加得到总数。
代码通过dp(n, x)计算[0, n]内数字x的出现次数最终结果为dp(b, x) - dp(a-1, x)。
关键函数解析
get(int l, int r)作用: 提取数字的高位部分。
示例: 若s [4,3,2]对应数字 234get(3,
返回23即高位部分s[3]和s[2]组成的数字。
p(int n)作用: 计算 10n10n的值。
dp(ll n, int x)步骤:拆位存储: 将数字n逆序存入数组s如234存储为s[1]4, s[2]3, s[3]2。
逐位分析: 从最高位到最低位遍历每一位i计算x在该位的出现次数。
分情况计算:高位自由组合: 当x小于当前位的值低位可以任意取值。
高位受限: 当x等于当前位的值低位受限于原始数字。
以输入100 234为例分析数字0的统计过程
计算dp(234,
拆位:s [4,3,2],k3。
遍历每一位:十位 (i
:高位部分:get(3,
2计算(2-
*10^1 10高位允许
共 2 种情况但x0时高位不能全为 0。
低位自由组合: 因0 3低位可以取
加10。
累计结果:10 10 20。
个位 (i
:高位部分:get(3,
23计算(23-
*10^0 22。
低位自由组合: 因0 4加1。
累计结果:22 1 23总和20 23 43。
计算dp(99,
拆位:s [9,9],k2。
遍历每一位:十位 (i
:高位部分:get(2,
越界不计入。
个位 (i
:高位部分:get(2,
9计算(9-
*1 8。
低位自由组合: 因0 9加1。
累计结果:8 1 9。
最终结果区间[100, 234]中0的出现次数:43 - 9 34
经典案例1[洛谷P2602 数字计数] — 方法2深搜记忆化递归AC代码#includebits/stdc.husingnamespacestd;typedeflonglongll;//pos:当前处理的位置//cnt当前数字出现的次数//limit是否受到上限限制//lead是否有前导0ll dp[15][15][2][2];//dp[pos][cnt][limit][lead]inta[15];//存储数字的每一位inttarget;//当前统计的目标数字(0-
lldfs(intpos,intcnt,boollimit,boollead){if(pos-
returncnt;//递归终点返回当前数字的出现次数if(dp[pos][cnt][limit][lead]!-
{returndp[pos][cnt][limit][lead];//记忆化}intuplimit?a[pos]:9;//当前位的上限ll res0;for(inti0;iup;i){intnew_cntcnt(itarget);//更新当前数字的出现次数if(leadi
new_cnt0;//前导0不计入统计boolnew_limitlimit(iup);boolnew_leadlead(i
;resdfs(pos-1,new_cnt,new_limit,new_lead);}returndp[pos][cnt][limit][lead]res;//记忆化}llsolve(ll x){intpos0;while(x){a[pos]x%10;//将数字拆分为每一位x/10;}memset(dp,-1,sizeof(dp));//初始化DP数组returndfs(pos-1,0,true,true);//从最高位开始搜索}intmain(){ll a,b;cinab;for(inti0;i9;i){targeti;//设置当前统计的目标数字ll anssolve(b)-solve(a-
;//计算区间[a,b]内的出现次数coutans ;}return0;}解题思路数位DP将问题转化为统计[1, b]和[1, a-1]中每个数字出现的次数然后相减。
状态设计pos当前处理的数位位置。
limit当前是否受到上限限制。
lead是否有前导零。
cnt当前数字的出现次数。
记忆化搜索通过 DP 数组缓存中间结果避免重复计算。
代码分析DFS 函数pos当前处理的数位位置。
cnt当前数字target的出现次数。
limit是否受到上限限制。
lead是否有前导零。
递归终点当pos -1时返回当前数字的出现次数cnt。
记忆化通过dp[pos][cnt][limit][lead]缓存结果避免重复计算。
状态转移遍历当前位的所有可能值i从0到up。
更新new_cnt如果i target则cnt加 1。
处理前导零如果lead为true且i 0则new_cnt重置为 0。
更新limit和lead状态。
Solve 函数将数字x拆分为每一位存储在数组a中。
初始化 DP 数组为-1。
调用dfs函数从最高位开始搜索。
主函数输入区间[a, b]。
对每个数字
调用solve函数计算其在[a, b]内的出现次数并输出结果。
复杂度分析时间复杂度O(10×log10(b)×10×2×
其中10是数字范围log10(b)是数字位数10是cnt的范围2是limit和lead的状态数。
空间复杂度O(15×15×2×
用于存储 DP 数组。
经典案例2[洛谷P2657 windy数] — 方法深搜记忆化递归AC代码#includebits/stdc.husingnamespacestd;/* pos当前处理位0~14 pre前一位的值0~9 特殊标记10表示前导零 limit当前位是否受原数字限制0/1 lead是否为前导零状态0/1 */inta[15];intdp[15][11][2][2];//pre中的10表示前导0状态intdfs(intpos,intpre,intlimit,intlead){if(pos-
returnlead?0:1;//递归终点全前导零返回0否则返回1找到一个合法数if(dp[pos][pre][limit][lead]!-
returndp[pos][pre][limit][lead];intuplimit?a[pos]:9;// 当前位最大值受原数字限制intres0;// 当前状态下的合法数字个数for(inti0;iup;i){// 遍历当前位所有可能取值if(!leadabs(i-pre)
continue;// 剪枝非前导零时检查相邻差是否≥2// 更新状态boolnew_leadlead(i
;// 是否仍是前导零intnew_prenew_lead?10:i;// 前导零时pre标记为10boolnew_limitlimit(iup);// 更新limitresdfs(pos-1,new_pre,new_limit,new_lead);}returndp[pos][pre][limit][lead]res;// 记忆化}intsolve(intx){if(x
return0;// 直接处理x0的情况intpos0;while(x){// 拆分数位到a数组a[pos]x%10;x/10;}memset(dp,-1,sizeof(dp));// 重置记忆化数组returndfs(pos-1,10,true,true);// 初始状态最高位、pre10前导零、limittrue、leadtrue}intmain(){inta,b;cinab;coutsolve(b)-solve(a-
;return0;}代码功能解析
全局变量与数据结构int a[20]; // 存储数字的每一位逆序低位在前 int dp[20][11][2][2]; // 记忆化数组pos(位)、pre(前一位值)、limit(是否受限)、lead(前导零)a数组存放待处理数字的每一位例如数字234存储为a [4,3,2]pos从0开始。
dp数组四维记忆化数组维度分别为pos当前处理位0~19pre前一位的值0~9 特殊标记10表示前导零limit当前位是否受原数字限制0/1lead是否为前导零状态0/
核心函数dfsint dfs(int pos, int pre, int limit, int lead) { if (pos -
{ return lead ? 0 : 1; // 递归终点全前导零返回0否则返回1找到一个合法数 } if (dp[pos][pre][limit][lead] ! -
return dp[pos][pre][limit][lead]; int up limit ? a[pos] : 9; // 当前位最大值受原数字限制 int res 0; // 当前状态下的合法数字个数 for (int i 0; i up; i) { // 遍历当前位所有可能取值 // 剪枝非前导零时检查相邻差是否≥2 if (!lead abs(i - pre)
continue; // 更新状态 bool new_lead lead (i
; // 是否仍是前导零 int new_pre new_lead ? 10 : i; // 前导零时pre标记为10 bool new_limit limit (i up); // 更新limit res dfs(pos-1, new_pre, new_limit, new_lead); } return dp[pos][pre][limit][lead] res; // 记忆化 }递归终止条件pos -1时若仍有前导零leadtrue返回0如数字000无效否则返回1找到一个合法数字。
记忆化检查若当前状态已计算过直接返回缓存结果。
当前位取值范围若limittrue最大值是原数字的当前位值a[pos]否则为9。
状态转移前导零处理若当前位是前导零leadtrue且取值为0则new_lead保持为truepre标记为10。
相邻差判断若非前导零状态检查当前位与前一位的差值是否≥2否则跳过。
递归调用处理下一位更新limit若当前位已达上限则下一位受限。
初始化函数solvecpp复制int solve(int x) { if (x
return 0; // 直接处理x0的情况 int pos 0; while (x) { // 拆分数位到a数组 a[pos] x % 10; x / 10; } memset(dp, -1, sizeof(dp)); // 重置记忆化数组 return dfs(pos-1, 10, 1,
; // 初始状态最高位、pre10前导零、limit1 }拆分数位将数字x逆序存入a数组例如234存储为[4,3,2]。
初始调用从最高位开始递归pre10表示前导零状态limit1表示最高位受原数字限制。