2022-07-09：总长度为n的数组中，所有长度为k的子序列里，有多少子序列的和为偶数？
答案2022-07-09：
方法一：递归，要i还是不要i。
方法二：动态规划。需要两张dp表。
代码用rust编写。代码如下：
代码语言：rust复制use rand::Rng;
fn main() {
let nn: i32 = 20;
let vv: i32 = 30;
let test_time: i32 = 3000;
println!("测试开始");
for i in 0..test_time {
let n = rand::thread_rng().gen_range(0, nn) 1;
let k = rand::thread_rng().gen_range(0, n) 1;
let mut arr = random_array(n, vv);
let ans1 = number1(&mut arr, k);
let ans2 = number2(&mut arr, k);
if ans1 != ans2 {
println!("出错了!{}", i);
println!("ans1 = {}", ans1);
println!("ans2 = {}", ans2);
break;
}
}
println!("测试结束");
}
fn number1(arr: &mut Vec<i32>, k: i32) -> i32 {
if arr.len() == 0 || k < 1 || k > arr.len() as i32 {
return 0;
}
return process1(arr, 0, k, 0);
}
fn process1(arr: &mut Vec<i32>, index: i32, rest: i32, sum: i32) -> i32 {
if index == arr.len() as i32 {
return if rest == 0 && (sum & 1) == 0 { 1 } else { 0 };
} else {
return process1(arr, index 1, rest, sum)
process1(arr, index 1, rest - 1, sum arr[index as usize]);
}
}
fn number2(arr: &mut Vec<i32>, k: i32) -> i32 {
if arr.len() == 0 || k < 1 || k > arr.len() as i32 {
return 0;
}
let n = arr.len() as i32;
// even[i][j] : 在前i个数的范围上(0...i-1)，一定选j个数，加起来是偶数的子序列个数
// odd[i][j] : 在前i个数的范围上(0...i-1)，一定选j个数，加起来是奇数的子序列个数
let mut even: Vec<Vec<i32>> = vec![];
let mut odd: Vec<Vec<i32>> = vec![];
for i in 0..n 1 {
even.push(vec![]);
odd.push(vec![]);
for _ in 0..k 1 {
even[i as usize].push(0);
odd[i as usize].push(0);
}
}
for i in 0..=n {
// even[0][0] = 1;
// even[1][0] = 1;
// even[2][0] = 1;
// even[n][0] = 1;
even[i as usize][0] = 1;
}
for i in 1..=n {
for j in 1..=get_min(i, k) {
even[i as usize][j as usize] = even[(i - 1) as usize][j as usize];
odd[i as usize][j as usize] = odd[(i - 1) as usize][j as usize];
even[i as usize][j as usize] = if (arr[(i - 1) as usize] & 1) == 0 {
even[(i - 1) as usize][(j - 1) as usize]
} else {
odd[(i - 1) as usize][(j - 1) as usize]
};
odd[i as usize][j as usize] = if (arr[(i - 1) as usize] & 1) == 0 {
odd[(i - 1) as usize][(j - 1) as usize]
} else {
even[(i - 1) as usize][(j - 1) as usize]
};
}
}
return even[n as usize][k as usize];
}
fn get_min<T: Clone Copy std::cmp::PartialOrd>(a: T, b: T) -> T {
if a < b {
a
} else {
b
}
}
// 为了测试
fn random_array(n: i32, v: i32) -> Vec<i32> {
let mut ans: Vec<i32> = vec![];
for _i in 0..n {
ans.push(rand::thread_rng().gen_range(0, v));
}
return ans;
}执行结果如下：
在这里插入图片描述左神java代码
