pofk_algorithm 0.0.3

A collection of efficient algorithms implemented in Rust for real-world projects.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

//! Coin Change (Generic, Production-Grade)
//!
//! Finds the minimum number of coins needed to make up a given amount.
//!
//! # Type Parameters
//! * `T`: Value type. Must implement `Copy` + `Ord` + `Sub<Output = T>` + `From<u8>` + `Default`.
//!
//! # Example
//! ```rust
//! use pofk_algorithm::dp_algorithms::coin_change::*;
//! let coins = vec![1usize, 2, 5];
//! let amount = 11usize;
//! assert_eq!(coin_change(&coins, amount), 3); // 11 = 5+5+1
//! ```
use std::ops::Sub;

pub fn coin_change<T>(coins: &[T], amount: T) -> i32
where
    T: Copy + Ord + Sub<Output = T> + From<u8> + Default + Into<usize>,
{
    let amount_usize = <T as Into<usize>>::into(amount);
    let mut dp = vec![i32::MAX - 1; amount_usize + 1];
    dp[0] = 0;
    for i in 1..=amount_usize {
        for &coin in coins {
            let coin_usize = <T as Into<usize>>::into(coin);
            if coin_usize <= i {
                dp[i] = dp[i].min(dp[i - coin_usize] + 1);
            }
        }
    }
    if dp[amount_usize] == i32::MAX - 1 { -1 } else { dp[amount_usize] }
}