使用 cashes_used 收集使用过的各面额纸币
(cashes: &[u32], amount: u32, min_cashes: &mut [u32], cashes_used: &mut [u32])
| 2 | |
| 3 | // 使用 cashes_used 收集使用过的各面额纸币 |
| 4 | fn dp_rec_mc_show(cashes: &[u32], amount: u32, min_cashes: &mut [u32], cashes_used: &mut [u32]) -> u32 { |
| 5 | for denm in 1..=amount { |
| 6 | let mut min_cashe_num = denm ; |
| 7 | let mut used_cashe = 1; // 最小面额是 1 元 |
| 8 | for c in cashes.iter().filter(|&c| *c <= denm).collect::<Vec<&u32>>() { |
| 9 | let index = (denm - c) as usize; |
| 10 | let cashe_num = 1 + min_cashes[index]; |
| 11 | if cashe_num < min_cashe_num { |
| 12 | min_cashe_num = cashe_num; |
| 13 | used_cashe = *c; |
| 14 | } |
| 15 | } |
| 16 | |
| 17 | // 更新各金额对应的最小纸币数 |
| 18 | min_cashes[denm as usize] = min_cashe_num; |
| 19 | cashes_used[denm as usize] = used_cashe; |
| 20 | } |
| 21 | |
| 22 | min_cashes[amount as usize] |
| 23 | } |
| 24 | |
| 25 | // 打印输出各面额纸币 |
| 26 | fn print_cashes(cashes_used: &[u32], mut amount: u32) { |