动态规划解决 区间[A，B]中有多少个整数的位数之和是s，哪个是最小的？用c++实现

好的，下面是基于上面的分析，使用C++实现的代码：

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

const int INF = 0x3f3f3f3f;
const int MAXN = 20;
int f[MAXN][MAXN][MAXN * MAXN], num[MAXN], len;

int dfs(int pos, int cnt, int sum, bool limit) {
    if (pos == 0) {
        return (cnt == 0 && sum == 0) ? 1 : 0;
    }
    if (!limit && f[pos][cnt][sum] != -1) {
        return f[pos][cnt][sum];
    }
    int up = limit ? num[pos] : 9;
    int res = 0;
    for (int i = 0; i <= up; i++) {
        if (cnt - 1 >= 0 && sum - i * pos >= 0) {
            res += dfs(pos - 1, cnt - 1, sum - i * pos, limit && i == up);
        }
    }
    if (!limit) {
        f[pos][cnt][sum] = res;
    }
    return res;
}

int solve(int x, int s) {
    len = 0;
    while (x) {
        num[++len] = x % 10;
        x /= 10;
    }
    int res = INF;
    for (int i = 1; i <= s; i++) {
        memset(f, -1, sizeof(f));
        int cnt = dfs(len, i, s, true);
        res = min(res, cnt);
    }
    return res;
}

int main() {
    int A, B, s;
    cin >> A >> B >> s;
    int ans = solve(B, s) - solve(A - 1, s);
    cout << ans << endl;
    return 0;
}

其中，`dfs` 函数用于计算状态转移方程，`solve` 函数用于枚举位数和，求出在 $[A,B]$ 中满足条件的数字个数，然后取其中的最小值即可。

由于位数和最大只有 $162$，所以可以将第三个维度的数组大小设置为 $162$，这样即可通过本题。