还没懂dfs的数位dp，暂时只会预处理和枚举数位。

预处理的dp是从低位到高位的，

需要前导0是f[0][0] = 1；
不需要的是前导0for (int j = 1; j <= 9; j++) g[1][j] = 1;

对于一个查询x，从x的高位枚举到低位就能做下去了。

分享一道需要前导0和不需要前导0的好题： 22数

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6 + 5, mod = 1e9 + 7;
int f[11][11 * 9], g[11][11 * 9];
int a[11];
int get(int x)
{
    x++;
    int cnt = 0;
    while(x)
    {
        a[++cnt] = x % 10;
        x /= 10;
    }

    int ret = 0;
    for (int i = cnt - 1; i >= 1; i--) 
    {
        ret += g[i][i * 2]; //这里不需要前导0
    }
    // cout << ret << "\n";
    int sum = 0;
    for (int i = cnt; i >= 1; i--)
    {
        for (int j = 0 + (i == cnt); j < a[i]; j++)
        {
            if (cnt * 2 - sum - j < 0) continue;
            ret += f[i - 1][cnt * 2 - sum - j]; //这里需要前导9
        }
        sum += a[i];
    }
    return ret;
}
void solve()
{
    f[0][0] = 1;
    for (int i = 1; i <= 10; i++)
    {
        for (int j = 0; j <= i * 9; j++)
        {
            for (int k = 0; k <= 9; k++)
            {
                if (j < k) continue;
                f[i][j] += f[i - 1][j - k];
            }
        }
    }


    for (int j = 1; j <= 9; j++) g[1][j] = 1;
    for (int i = 1; i <= 10; i++)
    {
        for (int j = 0; j <= i * 9; j++)
        {
            for (int k = 0; k <= 9; k++)
            {
                if (j < k) continue;
                g[i][j] += g[i - 1][j - k];
            }
        }
    }

    int n;
    cin >> n;
    cout << get(n);
}
signed main()
{
    // ios::sync_with_stdio(0);
    // cin.tie(0);
    int tt = 1;
    // cin >> tt;
    while (tt--) solve();
    return 0;
}