likes
comments
collection
share

带你爬上数位DP这座大山，从此俯瞰coding面试

作者站长头像
站长
· 阅读数 69

数位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−1​xn−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…

转载自:https://juejin.cn/post/6900034094596358152
评论
请登录