数位dp

• 要求统计满足一定条件的数的数量
• 这些条件经过转化后可以使用数位的思想去理解和判断
• 输入会提供一个数字区间来作为统计的限制
• 上界很大，暴力枚举验证会超时

sample1

求a~b中不包含49的数的个数

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

int a, b, shu[20], dp[20][2];

int dfs(int len, bool if4, bool shangxian)
{
    if (len == 0)
        return 1;
    if (!shangxian && dp[len][if4])   //为什么要返回呢？可以画图理解当我们搜到3XXX时，程序运行到1XXX时就已经把3XXX之后的搜索完了，记忆化也是这个用意.
        return dp[len][if4];
    int cnt = 0, maxx = (shangxian ? shu[len] : 9);//找到每一位的上限
    for (int i = 0; i <= maxx; i++)
    {
        if (if4 && i == 9)//如果上一位是4且这一位是9则跳过
            continue;
        cnt += dfs(len - 1, i == 4, shangxian && i == maxx);  //只有之前有限制现在的达到了上限才能构成限制
    }
    return shangxian ? cnt : dp[len][if4] = cnt; //如果有限制，那么就不能记忆化，否则记忆的是个错误的数.
}

int solve(int x)
{
    memset(shu, 0, sizeof(shu));
    int k = 0;
    while (x)
    {
        shu[++k] = x % 10;  //保存a,b的数
        x /= 10;
    }
    return dfs(k, false, true);
}

int main()
{
    scanf("%d%d", &a, &b);
    printf("%d\n", solve(b) - solve(a - 1));

    //while (1);
    return 0;
}

sample2

求a~b之间有多少个不含前导0且相邻两个数字之差至少为2的正整数

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
int shu[100];
ll dp[100][100];
ll dfs(ll pos,bool limit,bool zero,int last)
{
    if(pos==-1)
    return 1;
    if(!limit&&!zero&&dp[pos][last]+1)
    return dp[pos][last];
    int up;
    if(limit)
    up=shu[pos];
    else
    up=9;
    ll tem=0;
    for(int i=0;i<=up;++i)
    {
        if(abs(last-i)<2)
        continue;
        if(zero&&i==0)
        tem+=dfs(pos-1,limit&&i==up,1,-22);
        else
        tem+=dfs(pos-1,limit&&i==up,0,i);
    }
    if(!limit&&!zero)
    dp[pos][last]=tem;
    return tem;

}
ll solve(ll t)
{
    memset(dp,-1,sizeof(dp));
    int ans=0;
    while(t)
    {
        shu[ans++]=t%10;
        t/=10;
    }
    return dfs(ans-1,1,1,-2);
}
int main()
{
    ll a,b;
    cin>>a>>b;
    printf("%lld",solve(b)-solve(a-1));
}