| 1 | // dp_rec_mc.rs |
| 2 | |
| 3 | fn dp_rec_mc(cashes: &[u32], amount: u32, min_cashes: &mut [u32]) -> u32 { |
| 4 | // 动态收集从 1 到 amount 的最小找零纸币数 |
| 5 | for denm in 1..=amount { |
| 6 | // 此 min_cashe_num 等于全用 1 元纸币找零的纸币数 |
| 7 | let mut min_cashe_num = denm; |
| 8 | for c in cashes.iter() |
| 9 | .filter(|&c| *c <= denm) |
| 10 | .collect::<Vec<&u32>>() { |
| 11 | let index = (denm - c) as usize; |
| 12 | |
| 13 | // 加 1 是因为当前最小找零数等于上一最小找零数加 1 张 c 面额纸币 |
| 14 | let cashe_num = min_cashes[index] + 1; |
| 15 | if cashe_num < min_cashe_num { |
| 16 | min_cashe_num = cashe_num; |
| 17 | } |
| 18 | } |
| 19 | min_cashes[denm as usize] = min_cashe_num; |
| 20 | } |
| 21 | |
| 22 | // 因为收集了所有的最小找零纸币数，所以直接返回 |
| 23 | min_cashes[amount as usize] |
| 24 | } |
| 25 | |
| 26 | fn main() { |
| 27 | let amount = 81u32; |