带你爬上数位DP这座大山，从此俯瞰coding面试
数位DP问题，解决的是一个区间内满足要求的数字的个数。力扣中的数位DP基本属于medium或者hard，同时这类问题也经常在coding面试中出现。网上有很多数位DP的模板，但是那种带一大堆状态变量的写法对于初学者来说很有压力。本菜鸡之前听到数位DP就会头大。今天挑选了一道入门模板题来了解一下数位DP的通法，硬刚数位DP，从此对数位DP不再畏惧！
计数问题
给定两个整数 a 和 b，求 a 和 b 之间的所有数字中0~9的出现次数。
vector<int> countBetween(int a,int b)
{
}
题目链接 www.acwing.com/problem/con…
思路
台阶1 将区间计数转化为单点问题
类似于前缀和的思想，由于计数肯定是单调的，假设我们已经知道了0-x中数字i的答案，那么
return count(b) - count(a - 1);
这样做的好处一是可以避免特殊处理起点和终点的繁琐，二是可以预处理避免重复求解。
台阶2 n位数问题
抛开一切算法，假设让你用笔计算这个问题，我们自然想到按照数字的位数来分类讨论。因此我们先考虑一个简单的问题，所有的n位数中，数字0-9中出现次数 cnt[n][i]。
我们知道，所有的个位数(n = 1: 0,1,2,3,4,5,6,7,8,9)，每个数字都出现了一次，即
cnt[1][i] = 1
那么n = 2,3,4..呢？我们自然想到通过低位来扩展到高位，通过将n位的大问题转化为其子问题n-1来解决，这就是数位上的计数问题适合用动态规划状态转移来解决的原因。
那么如何从低位n-1转移到高位n呢？我们可能很快地想到，由于n-1位中的答案cnt[n-1][i]已知，那么n位的答案其实就是添加了一个最高位，最高位上可选的数字有10种选择（先不考虑前导0），所以对于一个n位数，数字i的出现次数等于
cnt[n][i] = 10 * cnt[n-1][i]
但事实上这样会少算一部分答案，也就是当添加的最高位等于i时，后面不管是什么数字都会增加一次i出现的次数，而后面的数共有10n−110^{n-1}10n−1个，要额外加上这一部分。
可见，最高位也是我们要考虑的状态。因此我们添加一维状态，记录最高位。
我们定义状态dp[n][v][i]表示n位数中，最高位为v时，数字i出现的次数。状态转移如下
int f[N][N][N] = {}; // n位数 最高位为v 数字i出现的次数（统计数字j）
void dp()
{
for(int n = 1; n < N; n++) // 枚举所有位数 n
for(int v = 0; v < N; v++) // 枚举最高位 v
{
if(n == 1)
f[n][v][v] = 1;//如果只有一位数，那么每个数字都出现了一次
else
for(int j = 0; j < N; j++) // 统计数字 j
{
for(int k = 0; k < N; k++) // 所有以任意k为开头的后n-1位数中，数字j出现的次数贡献给n位数中出现的次数（不考虑当前最高位）
f[n][v][j] += f[n-1][k][j];
if(j == i)//特别地，如果当前最高位就是统计数字j，那么不管后边数字是什么都额外贡献一个出现次数（当前最高位）
f[n][v][j] += pow(10,n-1);
}
}
}
台阶3 利用n位数问题解决任意上界问题
我们刚才对n位数上的问题进行了分析，事实上是对0..到999..这个区间进行分析的，而由于原问题是一个具体数字作为上限，是不能自由地从0取到999...的，我们如何借用n位数上问题的答案呢？
对于所有0 - n-1位的数字，答案是不受这个上限影响的，因此可以按照上述方法直接获得。
for(int i = 1; i < n; i++)
for(int j = i != 1; j < N; j++)
ans += f[i][j][c];
而对于n位的数字，我们要格外小心，不能超过这个上界。
这里的用到的一个思想是，我们将每个问题分成取到上限ana_nan和取0∼an−10 \sim a_{n} - 10∼an−1之间的某个数两种情况考虑。为什么要这么做呢？ 假设题目给的数x=xn−1xn−2...x0‾ x = \overline{x_{n-1}x_{n-2}...x_0}x=xn−1xn−2...x0，其实，如果我们某一位的上限为没有取到上限ana_{n}an时，而选择的是0∼an−10 \sim a_n - 10∼an−1那么剩余位其实是可以自由地从0-999..的，也就是可以用到n-1位上的答案。
所以统计答案时分成了两个部分
第一部分是不考虑前缀中目标数字对答案的贡献。
for(int hv = 0; hv < v; hv ++)
ans += dp[i+1][hv][c];
第二部分是前缀中包含目标数字c的对答案额外的贡献。
假设都取到了最高位xix_ixi，last为前缀中目标数字c的个数，而当前位取0∼xi−10 \sim x_i - 10∼xi−1，那么答案的个数可以根据乘法原理计算：前缀中目标数字c的个数为last个，当前位上共有0 - v - 1共v个选择，而后缀中的数字可以随便取，有10i10^{i}10i个,所以对答案的贡献就是三者相乘。
ans += last * v * pow(10,i);
至此，我们完成了本题所有的难点。
代码
#include<iostream>
#include<cstdio>
#include<vector>
#include<cmath>
using namespace std;
const int N = 10;
int f[N][N][N] = {}; // n位数 最高位为v 数字i出现的次数（统计数字j）
void dp()
{
for(int n = 1; n < N; n++) // 枚举所有位数 n
for(int v = 0; v < N; v++) // 枚举最高位 v
{
if(n == 1)
f[n][v][v] = 1;//如果只有一位数，那么每个数字都出现了一次
else
for(int j = 0; j < N; j++) // 统计数字 j
{
for(int k = 0; k < N; k++) // 所有以任意k为开头的后n-1位数中，数字j出现的次数贡献给n位数中出现的次数（不考虑当前最高位）
f[n][v][j] += f[n-1][k][j];
if(j == v)//特别地，如果当前最高位就是统计数字j，那么不管后边数字是什么都额外贡献一个出现次数（当前最高位）
f[n][v][j] += pow(10,n-1);
}
}
}
int count(int a,int c) // 上限为a,数字c出现的次数
{
if(!a) return c==0;
vector<int> num;
while(a) num.push_back(a % 10),a /= 10;
int n = num.size();
int ans = 0,last = 0;//答案个数，前缀中数字c出现的次数
//1-n-1位数中的答案
for(int i = 1; i < n; i++)
for(int j = i != 1; j < N; j++)
ans += f[i][j][c];
//n位数中的答案
for(int i = n - 1; i >= 0; i--)
{
int x = num[i];
//取0 ~ x - 1
//后缀中数字c出现的次数
for(int v = (i == n - 1); v < x; v ++)
ans += f[i+1][v][c];
//前缀取到x而包含c,额外贡献的次数
ans += last * x * pow(10,i);
last += c == x;
//全部取到x
if(i == 0) ans += last;//上限a中的c的次数
}
return ans;
}
int main()
{
int a,b;
dp();
while(scanf("%d%d",&a,&b),a || b)
{
if(a > b) swap(a,b);//输入中有逆序
for(int k = 0; k < N; k++)
cout << count(b,k) - count(a - 1,k) << " ";
cout << endl;
}
}
通用模板
针对数位DP问题，我们有一个通用的代码模板，可以让你对陌生的数位DP问题建立快速的思考框架，代码如下：
int dp[N][N];//状态
void dp() //利用动态规划完成初始化
{
}
int count(int a)//求[0,a]之间满足要求的数字个数
{
//边界特判
if(!n) return ___ ;
//数位拆解
vector<int> num;
while(a) num.push_back(a % 10),a /= 10;
int ans = 0;//记录答案数量
int last = 0;//记录遍历时的历史信息
//从高位到低位遍历上限
for(int i = num.size() - 1; i >= 0)
{
//计数
ans += ___ ;
if( ___ )
last++;
}
return ans;
}
int solve(int a,int b)
{
dp();
return count(b) - count(a - 1);
}
感谢 yxc && www.acwing.com/solution/co…