给定一个包含数字和总和的字符串str作为输入。目标是找到直至str的数字总和等于总数的数字。
例如
输入-N =“ 110”和= 5
输出-具有给定数字总和的小于或等于N的数字计数为：7
说明-直到110的数字总和等于5的数字是：-
5、14、23、32、41、50和104。
输入-N =“ 1000” sum = 3
输出-具有给定数字总和的小于或等于N的数字计数为：10
说明-直到1000的数字之和等于3的数字是：-
3、12、21、30、102、111、120、201、210和300。
在这种方法中，我们将使用动态编程将数字和其数字的总和存储在数组arr [18] [2] [162]中。这里18表示最大的18位数字，2表示值0和1。并且162表示如果所有18位数字均为9（18 * 9 = 162），则可能的最大和。
元素arr [i] [j] [k]的值表示根据i个数字的当前构造数是小于还是大于i中的第一个i数来考虑前i个数字并且j为0或1的数字计数。 N。（如果N为123并且i为2，那么我们将检查2个数字是否等于或大于12。如果等于12，则j将为1，否则j在arr [i] [j] [k中将为0 ]）。索引k将是arr [i] [j] [k]中i个数字的总和。
如果i = N的数字且k =输入和，则结果将为1，否则为0。
为了填充下一个数字（i + 1th），我们将检查j。如果j为1，则i-1数字等于N的i-1数字，因此下一个数字只能具有介于N的第0到i + 1数字之间的值，以使其<=N。
如果j为0，则i-1位数小于N中的i-1位数。因此，对于下一个数字（i + 1 th）位置，我们可以将0到9之间的任何值放置，并且该数值仍小于N.
最后返回结果作为最终计数。
取代表数字N的字符串str，并将总数作为数字的总和。
取数组arr [18] [2] [162]并使用memset将其初始化为-1。
函数以count_digits(int i, bool check, int temp, int total, string str, int size)递归方式填充arr [] [] []，最后以给定的数字总和返回小于或等于N的数字的计数。
如果当前位数i等于N位数并且当前总和温度等于输入总和，则返回1，否则返回0。
取count = arr [i] [check] [temp]。如果不是-1，则返回count作为结果。
取临时变量check_2(bool)和temp_2。(int)。
使用for循环遍历数字0到9，并比较check是1还是0。如果为1，则将当前数字ch与str [i]进行比较。如果更大，则中断循环（不执行任何操作）。
设置check_2 =检查|| ch <str [i]。
将temp_2 = temp +（ch-'0'）设置为当前总和。
添加count_digits（i + 1，check_2，temp_2，total，str，size）进行计数以递归计算数字总和。
最后返回结果作为计数。
#include <bits/stdc++.h>
using namespace std;
int arr[18][2][162];
int count_digits(int i, bool check, int temp, int total, ing str, int size) {
if (i == size) {
if (temp == total) {
return 1;
} else {
return 0;
}
}
int count = arr[i][check][temp];
if (count != -1) {
return count;
}
count = 0;
bool check_2;
int temp_2;
for (char ch = '0'; ch <= '9'; ch++) {
if (!check) {
if (ch > str[i]) {
break;
}
}
check_2 = check || ch < str[i];
temp_2 = temp + (ch - '0');
count += count_digits(i + 1, check_2, temp_2, total, str, size);
}
return count;
}
int main() {
string str = "1101";
int size = str.size();
int total = 5;
memset(arr, -1, sizeof(arr));
cout << "具有给定数字总和的小于或等于N的数字计数为： " << count_digits(0, 0, 0, total, str, size);
return 0;
}如果我们运行上面的代码，它将生成以下输出-
输出结果
具有给定数字总和的小于或等于N的数字计数为： 26