const DENOMINATIONS : [usize; 15] = [500_00, 200_00, 100_00, 50_00, 20_00, 10_00, 5_00, 2_00, 1_00, 50, 20, 10, 5, 2, 1];

fn num_combinations(sum: usize) -> u128 {
	let mut cache = vec![[None; 15]; sum+1];
	num_combinations_inner(sum, 0, &mut *cache)
}

fn num_combinations_inner(sum: usize, min_index: usize, cache: &mut[[Option<u128>; 15]]) -> u128 {
    if let Some(res) = cache[sum][min_index] {
        // cache hit
		res
	} else {
	    // cache miss
		let res = DENOMINATIONS[min_index..]
			.into_iter()
			.enumerate()
			.map(|(i, &d)| {
				if sum > d {
				    // not there yet, so we recurse,
				    // making sure not to use any denominations larger than d
				    // (via min_index)
					num_combinations_inner(sum - d, min_index + i, cache)
				} else if sum == d {
				    // exact fit
					1
				} else {
				    // too much
					0
				}
			})
			.sum();
		// update cache
		cache[sum][min_index] = Some(res);
		res
	}
}

fn main() {
    println!("{}", num_combinations(1_000_00));
}