hdoj 2089 数位dp入门（Java版）

题目链接： 题目大意：告诉你两个区间a，b，问你在[a,b]中有多少个数字不包含4或者62（连续的）。 emm，之前去的icpc焦作区域赛的时候，热身赛有道题没做出来，后来听别人说是数位dp，就想练练这方面的题目，学学新的知识点，这题是我做的第一道数位dp的题目，推荐之前看的一个大佬讲的数位dp总结的博客，感觉很不错。链接： AC代码：

import java.util.Scanner;
/*
 * 数位dp入门题
 */
public class hdoj2089 {
	static int a[]=new int[10];
	static int dp[][]=new int[10][2];
	static int solve(int x){
		int pos=0;
		while(x!=0){
			a[pos++]=x%10;
			x/=10;
		}
		return dfs(pos-1,-1,0,true);
	}
	static int dfs(int pos,int pre,int sta,boolean limit){//分别代表当前位置，是否有前导0，是否有限制，不是每个题都要判断前导零
		//递归边界，既然是按位枚举，最低位是0，那么pos==-1说明这个数我枚举完了
		if(pos==-1)
			return 1;//这里一般返回1，表示你枚举的这个数是合法的，那么这里就需要你在枚举时必须每一位都要满足题目条件，也就是说当前枚举到pos位，一定要保证前面已经枚举的数位是合法的。不过具体题目不同或者写法不同的话不一定要返回1 */
		//第二个就是记忆化(在此前可能不同题目还能有一些剪枝)
		if(!limit&&dp[pos][sta]!=-1)
			return dp[pos][sta];
		int up=(limit?a[pos]:9);
		int tmp=0;
		for(int i=0;i<=up;i++){
			if(pre==6&&i==2)
				continue;
			if(i==4)
				continue;
			tmp+=dfs(pos-1,i,i==6?1:0,limit&&i==a[pos]);
		}
		if(!limit)
			dp[pos][sta]=tmp;
		return tmp;
	}
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int n,m;
		for(int i=0;i<10;i++){
			for(int j=0;j<2;j++){
				dp[i][j]=-1;
			}
		}
		while(true){
			n=sc.nextInt();
			m=sc.nextInt();
			if(n==0&&m==0){
				break;
			}
			System.out.println(solve(m)-solve(n-1));
		}
		sc.close();
	}
}