最小紙幣找零算法

coin_change.rs

// 最小紙幣找零算法
// 1. 用最大的紙幣找零
// 2. 用次大的紙幣找零

fn coin_change(coins: Vec<i32>, amount: i32) -> i32 {
    let mut coins = coins.iter().map(|&x| x as usize).collect::<Vec<_>>();
    coins.sort();
    let amount = amount as usize;
    let mut dp = vec![amount + 1; amount + 1];
    dp[0] = 0;
    for i in 1..=amount {
        for j in 0..coins.len() {
            if i >= coins[j] {
                dp[i] = std::cmp::min(dp[i], dp[i - coins[j]] + 1);
            }
        }
    }
    if dp[amount] == amount + 1 {
        return -1;
    }
    dp[amount] as _
}

fn cal(coins: &Vec<i32>, amount: i32) -> i32 {
    if coins.len() == 0 {
        return -1;
    }
    if amount == 0 {
        return 0;
    }
    if amount < coins[coins.len() - 1] {
        let mut coins = coins.clone();
        coins.pop();
        return cal(&coins, amount);
    } else {
        let result = cal(coins, amount - coins[coins.len() - 1]);
        if result != -1 {
            return result + 1;
        } else {
            let mut coins = coins.clone();
            coins.pop();
            return cal(&coins, amount);
        }
    }
}


#[test]
fn test2() {
    assert_eq!(coin_change(vec![1, 2, 5], 11), 3);
    assert_eq!(coin_change(vec![2], 3), -1);
    assert_eq!(cal(&vec![1, 2, 5], 11), 3);
    assert_eq!(cal(&vec![2], 3), -1);
}