描述
给定一个区间,为在这个区间当中[0,9]每个数字出现在各个数位上的次数
思路
- 数位dp模板题目,设表示考虑到第位,要计算的数是,并且之前出现了次的方案数,采用记忆化搜索的方式进行dp
- 采用dfs进行数位dp,具体的转移方法比较晦涩,可以参考代码注释
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll f[15][10][15];
int num[15];
ll dfs(int now,bool e,bool first,int target,int t)
/*
now表示当前的数位
e表示是否贴上界
first表示是否为第1个数位
target表示计算的值
t表示之前出现了几次target
*/
{
if(now==-1)
return t;//如果数位考虑完,返回出现的次数
if((!e)&&(!first)&&f[now][target][t]!=-1)
return f[now][target][t];//记忆化搜索
int u=e?num[now]:9;//计算当前可以遍历的最大的数
ll res=0;
if(first)//如果是第一个数且当前数位不填的情况
res+=dfs(now-1,false,true,target,t);
for(int i=first?1:0;i<=u;i++)//第一个数填写的情况
res+=dfs(now-1,(i==u)&e,false,target,t+(i==target));
return (e|first)?res:f[now][target][t]=res;//当不贴上界且不是第一个数的时候,将结果更新到记忆化数组当中
}
ll get(ll x,int target)
{
int now=0;
while(x)
{
num[now++]=x%10;
x/=10;
}
return dfs(now-1,true,true,target,0);
}
int main()
{
memset(f,-1,sizeof(f));
ll a,b;
scanf("%lld%lld",&a,&b);
for(int i=0;i<=9;i++)
{
printf("%lld ",get(b,i)-get(a-1,i));
}
puts("");
}
时间复杂度,空间复杂度