2023-04-10：给定两个正整数x、y，都是int整型(java里)
返回0 ~ x以内，每位数字加起来是y的数字个数。
比如，x = 20、y = 5，返回2，
因为0 ~ x以内，每位数字加起来是5的数字有：5、14，
x、y范围是java里正整数的范围，
x <= 2 * 10^9，
y <= 90。
输入：1000，4。
输出：15。
输入：2000，6。
输出：49。
来自CISCO。
答案2023-04-10：
本文介绍了两种解决给定 x 和 y，求 0~x 中每位数字之和为 y 的数字个数的方法。第一种方法使用暴力枚举的方式，遍历 0~x 中的每一个数字，计算其每位数字之和是否等于 y，并统计符合条件的数字数量。第二种方法使用动态规划的思想，通过数位 DP 的方式快速计算符合条件的数字数量。
1. 暴力枚举法
暴力枚举法是一种朴素的解题思路，对于每个数字，我们可以循环计算其每位数字之和，然后判断是否等于 y，如果是，则计数器加 1。这种方法看似简单，但由于需要遍历 x 个数，时间复杂度为 O(x * log(x))，不能满足本题要求的时间复杂度。
2. 数位 DP
数位 DP 是一种常见的动态规划思想，主要用于解决与数字相关的问题。其基本思路是将数字按照位数拆分，然后根据各位数字的限制条件（如数字大小、数字和等）进行状态转移，最终得到答案。
本题中，我们可以使用数位 DP 来计算符合条件的数字数量。具体来说，假设当前处理到数字 x 的第 i 位，已经确定前 i-1 位的数字为 num，则当前的状态可以表示为 (i, num, sum)，其中 sum 表示前 i 位数字之和。根据此状态定义，我们可以设计转移方程如下：
如果 i == 0，则返回 sum 是否等于 y 的结果，即 count(x, i, num, sum) = if sum == y {1} else {0}。
否则，设当前处理到的数字为 cur，则有两种情况：
当 cur <= sum 时，对答案的贡献为 get_form(i-1, sum-cur)，即在第 i-1 位上选择符合条件的数字，然后将其放在当前位置上。
当 cur == x / offset % 10 时，需要递归计算下一位数字的方案总数，即 count(x, i-1, num cur*offset, sum-cur)。
最终的答案为 count(x, len, 0, y)，其中 len 表示数字 x 的位数，offset 表示当前处理到的位数所代表的权值。
为了提高效率，我们可以使用记忆化搜索来避免重复计算。具体来说，我们可以使用一个二维数组 dp 来记录已经计算过的状态，如果当前状态已经被计算过，则直接返回其对应的结果。
同时，由于在转移方程中需要频繁地查询 get_form(i, sum) 函数，这会导致函数调用次数过多，降低程序效率。因此，我们可以在程序运行前先预处理出所有可能的状态下的方案数，然后使用静态数组保存结果，在程序运行时直接查询即可。
综上所述，本题的数位 DP 解法时间复杂度为 O(log(x) * y)，空间复杂度为 O(log(x) * y)。相比于暴力枚举法，数位 DP 基于动态规划的思想，通过状态转移方程快速计算答案，具有更高的效率和更好的可拓展性。
rust代码如下：
代码语言：javascript复制fn num1(x: i32, y: i32) -> i32 {
let mut ans = 0;
for i in 0..=x {
if check1(i, y) {
ans = 1;
}
}
ans
}
fn check1(num: i32, y: i32) -> bool {
let mut sum = 0;
let mut n = num;
while n != 0 {
sum = n % 10;
n /= 10;
}
sum == y
}
fn num2(x: i32, y: i32) -> i32 {
if x < 0 || y > 90 {
return 0;
}
if x == 0 {
return if y == 0 { 1 } else { 0 };
}
let mut offset = 1;
let mut len = 1;
while offset <= x / 10 {
offset *= 10;
len = 1;
}
let mut dp = vec![vec![-1; (y 1) as usize]; (len 1) as usize];
count(x, offset, len, y, &mut dp)
}
fn count(x: i32, offset: i32, len: i32, rest: i32, dp: &mut Vec<Vec<i32>>) -> i32 {
if len == 0 {
return if rest == 0 { 1 } else { 0 };
}
if dp[len as usize][rest as usize] != -1 {
return dp[len as usize][rest as usize];
}
let mut ans = 0;
let cur = (x / offset) % 10;
for i in 0..cur.min(rest 1) {
ans = get_form((len - 1) as usize, (rest - i) as usize);
}
if cur <= rest {
ans = count(x, offset / 10, len - 1, rest - cur, dp);
}
dp[len as usize][rest as usize] = ans;
ans
}
// 打表
const FORM_SIZE: usize = 11;
const FORM_SUM: usize = 91;
static mut FORM: [[i32; FORM_SUM]; FORM_SIZE] = [[0; FORM_SUM]; FORM_SIZE];
fn init_form() {
unsafe {
FORM[0][0] = 1;
for len in 1..=10 {
for sum in 0..=len * 9 {
for cur in 0..=9.min(sum as i32) {
FORM[len as usize][sum as usize] =
FORM[(len - 1) as usize][(sum - cur) as usize];
}
}
}
}
}
fn get_form(len: usize, sum: usize) -> i32 {
unsafe { FORM[len][sum] }
}
fn main() {
println!("{}", i32::MAX);
init_form();
println!("{}", num1(88739128, 37));
println!("{}", num2(88739128, 37));
println!("{}", num1(1000, 4));
println!("{}", num2(1000, 4));
println!("{}", num1(2000, 6));
println!("{}", num2(2000, 6));
}
