# 2023-04-10：给定两个正整数x、y，都是int整型(java里) 返回0 ~ x以内，每位数字加起

2023-04-10：给定两个正整数x、y，都是int整型(java里)

x、y范围是java里正整数的范围，
x <= 2 * 10^9，
y <= 90。

1. 暴力枚举法

1. 数位 DP

rust代码如下：

``````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));
}
``````

(=￣ω￣=)··· 暂无内容！

337

14

27

12