Problem 31 "Coin sums"

In the United Kingdom the currency is made up of pound (£) and pence (p). There are eight coins in general circulation:

1p, 2p, 5p, 10p, 20p, 50p, £1 (100p), and £2 (200p).

It is possible to make £2 in the following way:

1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p

How many different ways can £2 be made using any number of coins?

問 31 「硬貨の和」

イギリスでは硬貨はポンド£とペンスpがあり，一般的に流通している硬貨は以下の8種類である.

1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p).

以下の方法で£2を作ることが可能である．

1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p

これらの硬貨を使って£2を作る方法は何通りあるか?

use std::cmp::Ordering;

fn coin_change_combination(payment: usize, coins: &[usize]) -> u32 {
    assert!(payment > 0 && coins.len() > 0);
    let mut table = vec![vec![0u32; payment]; coins.len()];
    for c in 0..table.len() {
        for p in 0..table[c].len() {
            let v_no = if c == 0 { 0u32 } else { table[c - 1][p] };
            let v_we = match (p + 1).partial_cmp(&(coins[c])).expect("NaNs") {
                Ordering::Less => 0u32,
                Ordering::Equal => 1u32,
                Ordering::Greater => table[c][p - coins[c]],
            };
            table[c][p] = v_no + v_we;
        }
    }
    table[coins.len() - 1][payment - 1]
}

fn main() {
    let payment = 200usize;
    let coins = [1usize, 2, 5, 10, 20, 50, 100, 200];
    let comb = coin_change_combination(payment, &coins);

    println!("{}", comb);
    assert_eq!(comb, 73682);
    assert_eq!(coin_change_combination(8, &[1, 3, 5, 7]), 6);
    assert_eq!(coin_change_combination(3, &[1, 2]), 2);
    assert_eq!(coin_change_combination(2, &[1, 2]), 2);
    assert_eq!(coin_change_combination(1, &[1, 2]), 1);
    assert_eq!(coin_change_combination(5, &[2, 3]), 1);
    assert_eq!(coin_change_combination(5, &[1, 2, 3]), 5);
    assert_eq!(coin_change_combination(5, &[1]), 1);
    assert_eq!(coin_change_combination(2, &[3]), 0);
}