不要62 hdu2089（数位dp + 记忆化搜索）

数位dp热身题

题目:

求n-m中不含4和“62”的数的个数

分析:

dp[i][j] 表示在第i位不是极限位，且前一位是6（j = 1）， 或不是6（j = 0）的时候的要求数的个数。

代码：

#include <bits/stdc++.h>
using namespace std;
int digit[20];
int dp[20][2];

int dfs(int pos, int limit, int lastdigit)
{
	if(pos == -1) return 1;
	if(!limit && dp[pos][lastdigit == 6])
		return dp[pos][lastdigit == 6];
	int res = 0;
	int top = limit ? digit[pos] : 9;
	for(int i = 0; i <= top; i++)
	{
		if(i == 4 || (i == 2 && lastdigit == 6)) continue;
		res += dfs(pos - 1, limit && i == top, i);
	}
	if(!limit) dp[pos][lastdigit == 6] = res;
	return res;	
}

int solve(int n)
{
	int pos = 0;
	while(n)
	{
		digit[pos++] = n % 10;
		n /= 10;
	}
	return dfs(pos - 1, 1, 0);
}

int main()
{
	int n, m;
	while(cin >> n >> m && (n || m))
	{
		cout << solve(m) - solve(n - 1) << endl;
	}
}