动态规划-数位DP

今天给大家带来的是数位dp的题目，这类题目相关性比较强，大家可以看我之前的作品进行学习，同时今天会给大家带来几个我在做题中遇到的问题，可以更好的帮助大家理解。

注意点⚠️：

1.首先对于前导0的是否要放到dp数组中：可以看到昨天的二进制问题并没有在dp数组中处理st问题，但是今天的第一道问题处理了st问题，对于是否要加上前导0的判断，关键就是要在题意处理的条件是否与前导0相关，说白了就是前导0是否会影响正常计算。比方说在二进制中，题目只要求求解出1的个数，所以前导0并不会影响结果。而在第一道题中，计算两位数字之间的差值，那么对于数字前最开始的0就要进行判断用bool st。具体的分析可以看第一题的代码。

2.对于i和pos位置的理解：i表示的是当前正在处理数位也就是a[pos]的取值。

第一题

题目描述

小明以他的名字命名了一种数——小明数。

对于一个十进制的数，若任意相邻两个数位的差值的绝对值不超过 KK，则称其为小明数。

现小明给出一个区间 L,R，求区间L,R 一共有多少个小明数。

输入描述

第 1行为一个整数 T，表示测试数据数量。

输入仅一行，包含三个整数 K,L,R。

1≤T≤105, 0≤K≤9, 1≤L≤R≤109。

输出描述

输出共 T 行，每行一个整数，表示每组数据的答案。

#include using namespace std;using ll= long long;ll dp[20][2][20][20];ll a[20],k;ll dfs(int pos,bool limit,bool st,int is,int p1){ if(pos<0)return is==1; if(!limit&&dp[pos][st][is][p1]!=-1)return dp[pos][st][is][p1]; ll res=0; int up=limit?a[pos]:9; for(int i=0;i0),!st||is&&(abs(p1-i)>t; while(t--){ memset(dp,-1,sizeof(dp)); int l,r; cin>>k>>l>>r; cout<<f(r)-f(l-1)<<\'\\n\'; } return 0;}

易错点：

1.memset的位置放置错误，一般的memste放在循环外就可，但是对于这道题来说k的值在变，所以需要放到里面。

2.is的初值为1，是考虑了前置0对于is的影响

第二题

问题描述

在一个神奇的国度里，有一个叫做小熊的数学家。有一天，小熊接到了国王的任务，要求他找出从 1 到 n 的数中，满足每一位上的数字乘积小于等于 m 的数字个数。

小熊感到十分困惑，他意识到，这个问题凭他现在的能力根本无法解决。于是他选择了向你求助。

请你需要帮助小熊，计算出满足条件的数字的个数。

输入格式

输入两个整数 n（1≤n≤1018） 和 m（1≤m≤109），含义如题所述。

输出格式

输出一个整数，表示从 1 到 n 的数中，满足每一位上的数字乘积小于等于 m 的数字个数。

#include using namespace std;using ll=long long;mapdp[25][2];int a[25];ll m;ll dfs(int pos,bool limit,bool st,ll sum){ if(pos<0)return st&&sum<=m; if(!limit&&dp[pos][st].find(sum)!=dp[pos][st].end())return dp[pos][st][sum]; ll res=0; int up=limit?a[pos]:9; for(int i=0;i0),st?sum*i:i); } if(!limit)dp[pos][st][sum]=res; return res;}ll f(ll c){ int pos=0; while(c){ a[pos++]=c%10; c/=10; } return dfs(pos-1,true,0,0);}int main(){ ll n; cin>>n>>m; cout<<f(n)<<\'\\n\'; return 0;}

代码错误处：

1.if(pos<0)return st&&sum<=m;这个地方第一次写成if(st&&pos<0&&sum<=m)这样写是没有正确的返回值的，所以会产生运行错误。

2.mapdp[][]记忆化要写成dp[][][sum]，不要忘掉sum的部分

易错点：

1.

dp[pos][st][sum] 的访问逻辑

1. dp[pos]

• 取出 dp 数组中索引为 pos 的元素，类型为 map[2]（即长度为 2 的map数组）。

2. dp[pos][st]

• 从 map[2] 数组中取出索引为 st 的元素，类型为 map。
• st 只能是 0 或 1，对应前导零状态和有效数位状态。

3. dp[pos][st][sum]

• 对 map 类型的元素执行下标操作 [sum]，相当于：
  • find(sum)：查找键为 sum 的元素。
  • 若存在，返回对应的值；若不存在，插入键 sum 并返回默认值（int 类型默认值为 0

2.使用mapdp[][]存储而不是dp[][][sum]

map的优势：动态存储稀疏状态

仅存储有效状态

• map dp[23][2]中，每个map仅存储实际出现的sum值。例如：
  • 前导零状态（st=0）下，sum始终为0，只需存储键0。
  • 有效数位状态（st=1）下，sum为各位乘积，仅当sum≤m时有效（m≤1e9），键值范围大幅缩小。

说白了用map存储可以规避超过m的部分，同时因为数字很大，对于有些包含前置0的部分可以不存入dp里面，也就是sum不存在的情况，这是普通dp定义无法做到的。

3.dp[][].find(sum)!=dp[][].end()怎么理解

• dp[pos][st].find(sum) != dp[pos][st].end()：
  • dp[pos][st] 是一个map，存储该状态下的乘积结果。
  • find(sum) 查找键sum是否存在：
    • 若存在，返回的迭代器不等于end()，条件成立。
    • 若不存在，返回end()，条件不成立。

好了，今天的分享就到这里，对于这部分题目的难度其实还是很大的，希望大家可以关注收藏好好看看，这部分对于我们的提升还是很大的。