HDU-2089 补个最经典的数位DP

统计[0,N]区间不包含4且不包含62的整数个数。

状态设计：
DP[pos][0] 表示当前考虑pos位，不包含4和62，不以6结尾的统计数；
DP[pos][1] 表示不包含4和62，以6结尾的统计数；

状态转移时，只要跳过数字4和2接上6的转移即可。

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int dp[30][2];
int bit[30];
int dfs(int pos, int istop, int s){
    if (pos==-1) return 1;
    if (!istop && dp[pos][s]!=-1) return dp[pos][s];

    int lastbit = istop ? bit[pos] : 9;
    int ans = 0;
    for (int i=0;i<=lastbit;i++){
        if (i==4||(i==2&&s)) continue;
        ans += dfs(pos-1, istop&&i==lastbit, i==6);
    }

    if (!istop) dp[pos][s] = ans;
    return ans;
}

int calc(int n){
    if (n==0) return 1;
    int cnt = 0;
    while(n){
        bit[cnt++] = n%10;
        n /= 10;
    }
    memset(dp,-1,sizeof(dp));
    return dfs(cnt-1,1,0);
}

int main(){
    int n,m;
    while(~scanf("%d%d",&n,&m)&&(n||m)){
        printf("%d\n", calc(m)-calc(n-1));
    }
}