数位动态规划
数位动态规划是求解一个大区间[L, R]中间满足条件Q的所有数字的个数（或者和，或其他）的一种方法。它通过分析每一位上的数字，一般用 dp[len][digit][...] 来表示状态“len位长的数字，最高位数字为digit所具有的xx特性”，利用记忆化搜索保存中间结果，从而加快求解速度。
通过求 f(n) 从0到n中满足条件Q的数字的个数，则所求的结果为 f(R) - f(L-1).
大多数数位dp都可以用一个DFS函数来进行记忆化搜索：
//len数字的位数，digit最高位的值，end_flag 表示digit是否是第len位（从低位向高位数，个位为第1位） 的范围边界
int Dfs(int len, int digit, bool end_flag){
//超出边界
if (len <= 0 || digit > 9 || digit < 0)
return 0;
//记忆化搜索，如果之前已经求出来了，则返回。注意这里要求 end_flag为false
if (!end_flag && dp[len][digit] != -1)
return dp[len][digit]; // 最简单情况看数字是否满足要求
if (len == 1)
return dp[len][digit] = xxx; //如果当前位是边界数字N对应位的最大值，则下一位的范围只能从0到边界数字N的下一位的最大值。否则为0 到 9
int end = end_flag ? bits[len - 2] : 9; int ans = 0;
for (int i = 0; i <= end; i++){
ans += Dfs(len - 1, i, end_flag && (i==end));
}
if (!end_flag) //digit不是第len位的最高范围，则可以将结果缓存
dp[len][digit] = ans;
return ans;
}
题目大意
给定一个区间[L, R]，求区间内满足条件“数位上不含有4，且不含有62（62必须连续）”的数字的个数。
分析
直接套用模板
实现
#include<iostream>
#include<stdio.h>
using namespace std;
int dp[9][10];
int bits[8]; //用dfs进行记忆化搜索， dp[len][digit] 表示 len位数字，最高位为digit满足条件的个数. 这里对数字范围没有限制！
//搜索的时候，若要进行记忆化，需要 dp[len][digit]的结果对数字范围没有限制，因此需要判断 end_flag来决定是否进行记忆。 //len数字的位数，digit最高位的值，end_flag 表示digit是否是第len位（从低位向高位数，个位为第1位） 的范围边界
int Dfs(int len, int digit, bool end_flag){
//超出边界
if (len <= 0 || digit > 9 || digit < 0)
return 0;
//记忆化搜索，如果之前已经求出来了，则返回。注意这里要求 end_flag为false
if (!end_flag && dp[len][digit] != -1)
return dp[len][digit]; // 最简单情况看数字是否满足要求
if (len == 1)
return dp[len][digit] = (digit != 4);
if (digit == 4)
return dp[len][digit] = 0; //如果当前位是边界数字N对应位的最大值，则下一位的范围只能从0到边界数字N的下一位的最大值。否则为0 到 9
int end = end_flag ? bits[len - 2] : 9; int ans = 0;
for (int i = 0; i <= end; i++){
if (!(digit == 6 && i == 2)) //除去 62连续的情况
ans += Dfs(len - 1, i, end_flag && (i==end));
}
if (!end_flag) //digit不是第len位的最高范围，则可以将结果缓存
dp[len][digit] = ans;
return ans;
} //将数字n的各个位上的范围求出来，保存到bits数组中，返回数字n的长度
int Init(int n){
memset(bits, 0, sizeof(bits));
int k = 0;
while (n){
bits[k++] = n % 10;
n /= 10;
}
return k;
} int Solve(int n){
int len = Init(n);
//数字长度为len，则为了避免首位遍历从0到bits[len-1]，给数字增加一个前导0。
//len + 1位，首位为0，且0是最高位的边界
int ans = Dfs(len + 1, 0, true);
return ans;
}
int main(){
int m, n;
memset(dp, -1, sizeof(dp));
while (scanf("%d %d", &m, &n)){
if (m == 0 && n == 0)
break;
int ret1 = Solve(m-1);
int ret2 = Solve(n);
int ret = ret2 - ret1;
printf("%d\n", ret);
}
return 0;
}