动态规划：最简单的数位DP问题

其实早在几个月前打周赛的时候就碰到过数位dp的题，当时看题解都看不懂，然后去OI wiki上看依旧看不懂，于是我在acwing上打卡碰到这题直接摆烂了三天，今天好好总结一下，啃下这块硬骨头。 😫

今天只讨论最简单的数位DP题目：

数位 DP 的基本原理：

考虑人类计数的方式，最朴素的计数就是从小到大开始依次加一。但我们发现对于位数比较多的数，这样的过程中有许多重复的部分。例如，从 7000 数到 7999、从 8000 数到 8999、和从 9000 数到 9999 的过程非常相似，它们都是后三位从 000 变到 999，不一样的地方只有千位这一位，所以我们可以把这些过程归并起来，将这些过程中产生的计数答案也都存在一个通用的数组里。此数组根据题目具体要求设置状态，用递推或 DP 的方式进行状态转移。

数位 DP 中通常会利用常规计数问题技巧，比如把一个区间内的答案拆成两部分相减（即

那么有了通用答案数组，接下来就是统计答案。统计答案可以选择记忆化搜索，也可以选择循环迭代递推。为了不重不漏地统计所有不超过上限的答案，要从高到低枚举每一位，再考虑每一位都可以填哪些数字，最后利用通用答案数组统计答案。

实例分析

抽象化例子

实现

c
#include<bits/stdc++.h>
using namespace std;
const int N = 15;
typedef long long ll;
ll mi[N], dp[N];
int a[N], x, y;

ll get(int l, int r){
    ll ans = 0;
    for(int i = l; i >= r; i --)
        ans = ans * 10 + a[i];
    return ans;
}

ll slove(int n, int x)
{
    if(!n) return 0;
    
    int len = 0;
    int temp = n;
    //取出每一位数字
    while(n){
        a[++ len] = n % 10;
        n /= 10;
    }
    ll ans = 0;
    for(int i = len - !x; i >= 1; i --)
    {
				//情况1
        if(i < len)
            ans += (get(len, i + 1) - !x) * mi[i - 1];
        //
        if(x == a[i])
            ans += get(i - 1, 1) + 1;
        else if(x < a[i])
            ans += mi[i - 1];
    }
    return ans;
}


int main()
{
    //获得幂
    mi[0] = 1ll;
    for(int i = 1; i <= 10; i ++)
        mi[i] = 10 * mi[i - 1];
    
    while(cin >> x >> y, x || y)
    {
        if(x > y) swap(x, y);
        
        for(int i = 0; i < 10; i ++)
            printf("%lld ", slove(y, i) - slove(x - 1, i));
        puts("");
    }
    
    return 0;
}

小结

• 这道题搞清楚只能算我有了对数位DP这类题目最基本的求解能力，后边的路还很长。。

参考

• OI wiki - 数位DP
• bili 数位DP思路分析及求解数位统计问题-CSP/NOIP系列教程