数位DP

算法介绍

简单来说，数位DP就是在数的每一位上进行DP，可以说是另类的暴力枚举了。

相比于简单的暴力枚举来说，数位DP具有记忆化的特点。

其实我感觉数位DP和状压DP有一点类似。

也是对每一位来进行DP。

实现方式

刚好我们学长给我们贴了模板，那我就直接贴上来吧。

注意事项都是在代码里面了。

#include <iostream>
#include <iomanip>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <sstream>
#include <vector>
#define INF 0x3f3f3f3f
using namespace std;

typedef long long ll;
const int mod = 1e9 + 7;
const int maxn = 10005;
const double pi = acos(-1.0);

int l,r;
int a[maxn];

int dfs(int pos,int sta, bool lead/*前导 0，不是所有题目都有，题目不同不一样*/, bool limit/*判断数位上限*/)
{
    //递归边界
    if(pos == -1)
        return 1;//返回值因题而异
    //记忆化
    if(!limit && !lead && dp[pos][sta] == -1)
        return dp[pos][sta];
    int len = limit?a[pos]:9; //判断上限
    int ans = 0;
    //开始计数
    for(int i = 0; i < len; i ++)
    {
        //剪枝与状态转移
        if()
        else if()
        ans += dfs(pos - 1, sta/*转移的状态*/,lead && i == 0, limit && i == a[pos]);
    }
    //完成记忆化
    if(!limit)
        dp[pos][sta] = ans;
    return ans;

}

int solve(int x)
{
    int pos = 0;
    while(x) // 分解数位
    {
        a[pos ++] = x % 10;
        x /= 10;
    }
    return dfs(pos - 1, -1, true, true); // 开始对数位从高位进行枚举
}

int main()
{
    while(cin >> l >> r)
    {
        cout << solve(r) - solve(l - 1) << endl;
    }
    return 0;
}

典型例题

题目大意

给你两个数n和m，问在n和m区间中，有多少数是不含4和62的。

解题思路

可以用$dp[pos][s]$来表示前一位是否是6的所有情况。s为1的时候代表前一位为6，那么这一位就不能为2，当s为0的时候，代表前一位不为6，那么就不用特殊考虑。

完整代码

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 50;
int dp[N][5],num[N];

int dfs(int p,int s,bool limit) {
	if (p == -1)	return 1;
	if (!limit && dp[p][s])	return dp[p][s];
	int l = limit ? num[p] : 9;
	int ans = 0;
	for (int i = 0; i <= l; i++) {
		if (i == 4||(s && i == 2))	continue;
		ans += dfs(p - 1, i == 6, limit&&i == num[p]);
	}
	if (!limit)	dp[p][s] = ans;
	return ans;
}

int solve(int m) {
	int c = 0;
	while (m) {
		num[c++] = m % 10,m /= 10;
	}
	return dfs(c - 1, 0, true);
}

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