数位dp入门之HDU-2089详解

//HDU2089
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int a,b,shu[20],dp[20][2];
int dfs(int len,bool ifis6,bool shangxian)
//长度（也是第几位）、当前位置是否是6、是否有上限 
{
    if (len==0)
        return 1;
    if (!shangxian && dp[len][ifis6])
	//为什么要返回呢？可以画图理解当我们搜到3XXX时，程序运行到1XXX时就已经把3XXX之后的搜索完了，记忆化也是这个用意.
        return dp[len][ifis6];
    int cnt=0,maxx=(shangxian?shu[len]:9);
    for (int i=0;i<=maxx;i++)
    {
        if (i==4||ifis6&&i==2)
            continue;
        cnt+= dfs(len-1,i==6,shangxian&&i==maxx);  
		//只有之前有限制现在的达到了上限才能构成限制
    }
    return shangxian?cnt:dp[len][ifis6]=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()
{
	while(scanf("%d%d",&a,&b)!=EOF)
	{
		if(!a&&!b)
		return 0;
		printf("%d\n",solve(b)-solve(a-1));
	} 
    return 0;
}