数位DP与模板题

数位dp是一种计数用的dp，一般就是要统计一个区间[le,ri]内满足一些条件数的个数。所谓数位dp，字面意思就是在数位上进行dp咯。数位还算是比较好听的名字，数位的含义：一个数有个位、十位、百位、千位……数的每一位就是数位啦！

模板题

HDOJ2089 不要62
给出一个数字范围，求范围内不出现62和4的数字的数量

#include<cstdio>
#include<cstring>
int num[10];
int dp[10][2];
int dfs(int pos, int state, int limit)
{
    if (pos == -1)    return 1;  //枚举到最后一位，该数字合法
    if (!limit && dp[pos][state] != -1)        return dp[pos][state];  //记忆化搜索，之前已经搜到了没有限制的答案，那么就直接返回
    int up = limit ? num[pos] : 9;   //是否有限制
    int tmp = 0;
    for (int i = 0; i <= up; i++)
    {
        if (i == 4)    continue;
        if (state == 1 && i == 2)    continue;   //state记录的是上一位的状态
        tmp += dfs(pos - 1, i == 6, limit && i == num[pos]);
    }
    if (!limit)    dp[pos][state] = tmp;
    return tmp;
}
/*把数字每一位存入数组，进行记忆化搜索*/
int solve(int x)
{
    int pos = 0;
    while (x)
    {
        num[pos++] = x % 10;
        x /= 10;
    }
    return dfs(pos - 1, 0, 1);
}

int main()
{
    int n, m;
    while (scanf("%d%d", &n, &m) != EOF && (n || m))
    {
        memset(dp, -1, sizeof(dp));
        printf("%d\n", solve(m) - solve(n - 1));
    }
    return 0;
}

具体分析留坑