数位 DP

发表于 更新于 分类于

数位 DP

基础知识

可以对有上限的数字进行枚举（相当于考虑无限制情况下的预处理） 这样就允许了预处理

  • 三、前缀的用途（以1234为例，控制上界枚举）
  • 11**：满足的为1100-1199，所以下一位可以是0-9
  • 12**：满足的为1200-1234，所以下一位可以是0-3
  • 那么，1234要求的是——
  • 0000-0999
  • 1000-1199
  • 1200-1229
  • 1230-1233
  • 1234（本身） ## 例题1

序列中含有49子串的数量？

基本思想与方法

  • 预处理!

  • 以上题为例，定义dp数组的含义如下：

  • dp[i][0]，表示长度为i，且不含有49

  • dp[i][1]，表示长度为i，且不含有49，且最高位为9

  • dp[i][2]，表示长度为i，且含有49

  • 状态转移方程：

  • dp[0][0]=1; dp[0][1]=dp[0][2]=0;

  • //在前面加0~9的数字，减掉在9前面加4

  • dp[i][0]=10*dp[i-1][0]-dp[i-1][1];

  • dp[i][1]=dp[i-1][0];//最高位加9

  • //在本来含有49的前面加任意数，或者在9前面加4

  • dp[i][2]=10*dp[i-1][2]+dp[i-1][1];

算法核心（统计部分）

int bit[25];
long long calc(long long n)
{
    int len=0;
    while(n)
    {
        bit[++len]=n%10;
        n/=10;
    }
    bit[len+1]=0;
    bool flag=false;
    long long ans=0;
    for(int i=len;i>=1;i--)
    {
        ans+=dp[i-1][2]*bit[i];
        if(flag) ans+=dp[i-1][0]*bit[i];
        else if(bit[i]>4) ans+=dp[i-1][1];
        if(bit[i+1]==4&&bit[i]==9)
            flag=true;
    }
    if(flag) ans++;      //加上n本身
    return ans;
}

需要每一位的提取 bit数组

记忆化DFS-数位DP

另一种数位 DP 实现方式（强烈推荐）

代码

long long dfs(int n, bool is4, bool is_max)
{
    if(!n) return 1;
    if(!is_max && dp[n][is4]!=-1)  return dp[n][is4];
    long long ans = 0;
    int m = is_max? b[n]:9;
    for(int i = 0;i <= m;++i)
        if(!(is4 && i==9)) ans+=dfs(n-1,i==4,is_max && i==m);
    if(!is_max) dp[n][is4] = ans;
    return ans;
}

is_max前一位是不是数位最大值 函数计算的是不含49的序列数量 满情况 记忆化时需要 !is_max

数位DP模板

int dp[len][状态], b[10]; // dp数组要根据实际情况决定用几维的数组，b数组用来保存数字位
int dfs(int pos, int state, bool is_max){ //可以根据需要，增加state参数的数量
    if(pos==0) return 1;
    if(!is_max && ~dp[pos][state]) return dp[pos][state];
    int end = is_max? b[pos]:9; //如果前面放满了就只能循环到b[pos ]，否则到9
    int ans = 0;
    for(int i=0; i<=end; i++){
        if(满足某种条件)
            ans+=dfs(pos-1, state, is_max&&i==end); //最后一个参数：前面都放满,本位又最大
    }
    if(!is_max) dp[pos][state] = ans;
    return ans;
}

例题2 - 车牌号

int dp[10][10],b[10];
int dfs(int n,int t,bool is_max)
{
    if(!n) return 1;
    if(!is_max && dp[n][t]!=-1)
        return dp[n][t];
    int ans = 0 ;
    int m = is_max? b[n]:9;
    for(int i = 0;i <= m;++i)
    {
        if(i!= 4 &&!(t == 6 && i == 2))
            ans+=dfs(n-1,i,is_max && i==m);
    }
    if(!is_max) dp[n][t] = ans;
    return ans;
}
int solve(int x)
{
    int len;
    for(len = 0; x >0 ; x /= 10)
        b[++len] = x % 10;
    return dfs(len, 0, true);  //参数含义？
}
int main()
{
    int n,m;
    memset(dp,-1,sizeof(dp));
    while(scanf("%d%d",&n,&m)==2)
    {
        if(n == 0 && m == 0) break;
        printf("%d\n", solve(m) - solve(n-1));
    }
    return 0;
}

EG：258 49

记录2（-2个）位置的元素 (-1)位置的元素

5（-1个） 4（-1个）