| 1 | // rec_mc2.rs |
| 2 | |
| 3 | fn rec_mc2(cashes: &[u32], amount: u32, min_cashes: &mut [u32]) -> u32 { |
| 4 | // 全用 1 元纸币的最小找零纸币数量 |
| 5 | let mut min_cashe_num = amount; |
| 6 | |
| 7 | if cashes.contains(&amount) { |
| 8 | // 收集和当前待找零值相同的币种 |
| 9 | min_cashes[amount as usize] = 1; |
| 10 | return 1; |
| 11 | } else if min_cashes[amount as usize] > 0 { |
| 12 | // 找零值 amount 有最小找零纸币数，直接返回 |
| 13 | return min_cashes[amount as usize]; |
| 14 | } else { |
| 15 | for c in cashes.iter().filter(|&&c| c <= amount).collect::<Vec<&u32>>() { |
| 16 | let cashe_num = 1 + rec_mc2(cashes, amount - c, min_cashes); |
| 17 | // 更新最小找零纸币数 |
| 18 | if cashe_num < min_cashe_num { |
| 19 | min_cashe_num = cashe_num; |
| 20 | min_cashes[amount as usize] = min_cashe_num; |
| 21 | } |
| 22 | } |
| 23 | } |
| 24 | |
| 25 | min_cashe_num |
| 26 | } |
| 27 | |
| 28 | fn main() { |
| 29 | let amount = 90u32; |