Minimum Coin Change Problem

and space optimized Dynamic Programming Solution using tabulation and memoization in Rust Language.

Introduction

Minimum Coin change is another classical Dynamic Programming problem and is very similar to Coin Change Problem.

In this problem, you are given coins of various denomination, and each coin has infinite supply.

You have to tell Minimum number of coins that you can use to make the exact amount.

For Example : If coins are [1, 3, 4] and the amount is 6, the answer should be 2, because you can form the sum using coins [3, 3]

Recursive Solution

Recursive solution to this problem is pretty straightforward. At each step, you have 2 choices :

Exclude the given coin : We can exclude the given coin and find the answer with the remaining coins. In this, we simply call recursion using same amount, but n-1 coins.
Include the given coin : We can include the coin and again call recursion by reducing amount, but on same number of coins, because we can include and exclude same coin again.

We have to take minimum of both the cases.

If amount is 0, we can form it using 0 coins.

Also, if n is 0 and amount is not 0, we can not make the money. Hence, return Infinite value. We will take 10¹⁰ as our infinite value for this question.

Function

Here is the function using above algorithm

use std::cmp::min;

fn min_coin_change(coins:&Vec<usize>, amount : usize, n:usize) -> usize{

    let infinite = 10_000_000_000;
    // If amount is 0, we can make it without using coins
    if amount == 0 { return 0; }

    // If no coins left, but amount is not 0, we can not make the amount.
    // Hence, return infinite value
    if n==0 { return infinite; }

    // If current coin is greater than amount, we can not include it
    // Hence, compute recursively the coins of n-1
    if coins[n-1] > amount {
        return min_coin_change(coins, amount, n-1);
    }

    // Now we can either exclude or include current coin
    // If exclude, answer would be the min_coin_change of n-1 items
    // If include, answer would be reduce the amount by denomination
    // And calculate the min_coin_change of n items.
    // Because we can include the coin again

    // Return minimum of both cases.
    return min(min_coin_change(coins, amount, n-1),1+min_coin_change(coins, amount-coins[n-1], n));
}

With driver code

use std::cmp::min;

fn min_coin_change(coins:&Vec<usize>, amount : usize, n:usize) -> usize{

    let infinite = 10_000_000_000;
    // If amount is 0, we can make it without using coins
    if amount == 0 { return 0; }

    // If no coins left, but amount is not 0, we can not make the amount.
    // Hence, return infinite value
    if n==0 { return infinite; }

    // If current coin is greater than amount, we can not include it
    // Hence, compute recursively the coins of n-1
    if coins[n-1] > amount {
        return min_coin_change(coins, amount, n-1);
    }

    // Now we can either exclude or include current coin
    // If exclude, answer would be the min_coin_change of n-1 items
    // If include, answer would be reduce the amount by denomination
    // And calculate the min_coin_change of n items.
    // Because we can include the coin again

    // Return minimum of both cases.
    return min(min_coin_change(coins, amount, n-1),1+min_coin_change(coins, amount-coins[n-1], n));
}


// Driver Code

use std::io;
fn take_vector() -> Vec<usize> {
    let mut input = String::new();
    io::stdin().read_line(&mut input).unwrap();
    let arr: Vec<usize> = input.trim().split_whitespace()
        .map(|x| x.parse().unwrap()).collect();
    return arr;
}

fn main() {
    let coins = take_vector();
    let amount = take_vector()[0];
    let ans  = min_coin_change(&coins, amount, coins.len());

    // If answer is infinity, we have to print -1
    if ans >= 1_000_000_000 { println!("-1"); }
    else { println!("{}", ans); }
}

Input

1 3 4
6

Output

2

Time Complexity : O( 2ⁿ )
Space Complexity : O( n )

( Space complexity includes recursive stack space )

Overlapping Sub-problems

If we have a look carefully on recursive approach, we computed multiple results many times.

For example, if coins are [1, 2, 3, 6, 12] and amount is 24, the result for n = 2 and amount = 12 is calculated 4 times, and takes many recursions each time. These are called overlapping sub-problems, because it is a sub-problem of actual problem and is overlapping in multiple recursions.

To prevent this, we can store the output and each result will be calculated only once.

In minimum coin change problem, we can create a dp matrix, and store each value by coin index and amount. That is, if we consider first i coins, the result will be stored at dp[i][amount].

This is called memoization or Top-down Dynamic Programming.

Memoization ( Top-down DP ) Method

In memoization method, we simply take a DP matrix, and store the computed result.

Algorithm

If the stored value for given number of coins and amount in DP matrix is not None, we return the value.
If the amount is 0, return 0 and if n is 0 and amount > 0, return infinity.
Else, use recursive logic to calculate the given value and store it in the DP matrix.

Function

Here is the function using above algorithm

use std::cmp::min;

fn min_coin_change(coins:&Vec<usize>, amount : usize, n:usize, dp : &mut Vec<Vec<Option<usize>>>) -> usize{

    let infinite = 10_000_000_000;
    // If amount is 0, we can make it without using coins
    if amount == 0 { return 0; }

    // If no coins left, but amount is not 0, we can not make the amount.
    // Hence, return infinite value
    if n==0 { return infinite; }

    // If already computed the value, return it
    if dp[n][amount].is_some() {
        return dp[n][amount].unwrap();
    }

    // If current coin is greater than amount, we can not include it
    // Hence, compute recursively the coins of n-1
    if coins[n-1] > amount {
        dp[n][amount] = Option::from(min_coin_change(coins, amount, n-1, dp));
        return dp[n][amount].unwrap();
    }

    // Now we can either exclude or include current coin
    // If exclude, answer would be the min_coin_change of n-1 items
    // If include, answer would be reduce the amount by denomination
    // And calculate the min_coin_change of n items.
    // Because we can include the coin again

    // Return minimum of both cases.
    dp[n][amount] =Option::from( min(min_coin_change(coins, amount, n-1, dp),1+min_coin_change(coins, amount-coins[n-1], n, dp)) );
    return dp[n][amount].unwrap();
}

With driver code

use std::cmp::min;

fn min_coin_change(coins:&Vec<usize>, amount : usize, n:usize, dp : &mut Vec<Vec<Option<usize>>>) -> usize{

    let infinite = 10_000_000_000;
    // If amount is 0, we can make it without using coins
    if amount == 0 { return 0; }

    // If no coins left, but amount is not 0, we can not make the amount.
    // Hence, return infinite value
    if n==0 { return infinite; }

    // If already computed the value, return it
    if dp[n][amount].is_some() {
        return dp[n][amount].unwrap();
    }

    // If current coin is greater than amount, we can not include it
    // Hence, compute recursively the coins of n-1
    if coins[n-1] > amount {
        dp[n][amount] = Option::from(min_coin_change(coins, amount, n-1, dp));
        return dp[n][amount].unwrap();
    }

    // Now we can either exclude or include current coin
    // If exclude, answer would be the min_coin_change of n-1 items
    // If include, answer would be reduce the amount by denomination
    // And calculate the min_coin_change of n items.
    // Because we can include the coin again

    // Return minimum of both cases.
    dp[n][amount] =Option::from( min(min_coin_change(coins, amount, n-1, dp),1+min_coin_change(coins, amount-coins[n-1], n, dp)) );
    return dp[n][amount].unwrap();
}


// Driver Code

use std::io;
fn take_vector() -> Vec<usize> {
    let mut input = String::new();
    io::stdin().read_line(&mut input).unwrap();
    let arr: Vec<usize> = input.trim().split_whitespace()
        .map(|x| x.parse().unwrap()).collect();
    return arr;
}

fn main() {
    let coins = take_vector();
    let amount = take_vector()[0];

    // Make a DP Matrix
    // Initially set all the elements to None
    let mut dp = vec![vec![Option::None; amount+1 ]; coins.len()+1];

    let ans  = min_coin_change(&coins, amount, coins.len(), &mut dp);

    // If answer is infinity, we have to print -1
    if ans >= 1_000_000_000 { println!("-1"); }
    else { println!("{}", ans); }
}

Input

1 3 4
6

Output

2

Time Complexity : O( n×amount )
Space Complexity : O( n×amount )

Tabulation ( Bottom-up DP ) Method

Although time and space complexities of tabulation as well as memoization method are same, tabulation is much more efficient as there are a lot of expensive recursive calls in memoization.

In tabulation method, we make the matrix, and fill it first on the basis of base condition, and then on the basis of previous row.

Algorithm

Initially, set first row to infinity, because if n == 0, we can not make amount, except when amount = 0. Also, set first column as 0, because if amount is 0, there is always amount can be formed in 1 step.
For all the amount for a given value of n, run below statement 3 and 4.
Set the values before the coin value as copied from above row, because we can not include a coin if its value is less than the amount.
Set the value of dp[i][amount] as minimum of including and excluding the given coin.
Return the dp[n][amount] as the final answer.

Function

Here is the function using above algorithm

use std::cmp::min;

fn min_coin_change(coins:&Vec<usize>, amount : usize, n:usize) -> usize{

    // Initially, set whole matrix to infinity
    let infinite = 10_000_000_000;
    let mut dp = vec![vec![infinite; amount+1]; n+1];

    // Set the first column to 0, because if amount is 0, we can make the amount
    for i in 0..n+1 { dp[i][0] = 0; }

    // Run loop for all the i from 1 to n
    for i in 1..n+1 {
        // Run loop for each amount below coins[n-1], set above row
        for j in 1..min(coins[i-1], amount+1){ dp[i][j] = dp[i-1][j]; }

        // Now, for larger amount, we can both include and exclude.
        // So, we take minimum of both cases
        for j in coins[i-1]..amount+1 {
            dp[i][j] = min(1+dp[i][j-coins[i-1]] , dp[i-1][j]);
        }
    }

    // Return The answer
    dp[n][amount]
}

Use the same driver code as recursive solution.

Input

1 3 4
6

Output

2

Time Complexity : O( n×amount )
Space Complexity : O( n×amount )

Space Optimized Tabulation Method

If we observe the above tabulation method carefully, we find that for calculating the minimum coin change for a given amount and number of coins, only current and previous row is required.

In the above algorithm, step 1 is base case or initialization step, and do not require any other row.

Step 3 and Step 4 requires only previous and current row.

Hence, we can optimize our space complexity, by storing only the previous row instead of the whole matrix.

Function

Here is the function using space optimization of tabulation method.

use std::cmp::min;

fn min_coin_change(coins:&Vec<usize>, amount : usize, n:usize) -> usize{

    // Initially, set previous as well as current to infinity
    let infinite = 10_000_000_000;

    let mut prev = vec![infinite; amount+1];
    let mut curr = vec![infinite; amount+1];

    // Set the first column to 0, because if amount is 0, we can make the amount
    prev[0] = 0;
    curr[0] = 0;

    // Run loop for all the i from 1 to n
    for i in 1..n+1 {
        // Run loop for each amount below coins[n-1], set above row
        for j in 1..min(coins[i-1], amount+1){ curr[j] = prev[j]; }

        // Now, for larger amount, we can both include and exclude.
        // So, we take minimum of both cases
        for j in coins[i-1]..amount+1 {
            curr[j] = min(1+curr[j-coins[i-1]] , prev[j]);
        }

        // Move the elements from current to previous
        for j in 0..amount+1 { prev[j] = curr[j];}
    }

    // Return The answer
    curr[amount]
}

Use the same driver code as recursive solution.

Input

1 3 4
6

Output

2

Time Complexity : O( n×amount )
Space Complexity : O( amount )

Conclusion

Minimum Coin change is another classical Dynamic Programming problem and is very similar to Coin Change Problem.

In this problem, you are given coins of various denomination, and each coin has infinite supply.

You have to tell Minimum number of coins that you can use to make the exact amount.

In this article, we saw how to solve the minimum coin change problem, first using recursion and then using Dynamic Programming, memoization as well as tabulation method, and latter the space optimized tabulation method in Rust Language.

Here is the optimized function for easy access

use std::cmp::min;
fn min_coin_change(coins:&Vec<usize>, amt : usize, n:usize) -> usize{
    let inf = 10_000_000_000;
    let mut p = vec![inf; amt+1];
    let mut c = vec![inf; amt+1];
    p[0] = 0; c[0] = 0;
    for i in 1..n+1 {
        for j in 1..min(coins[i-1], amt+1){ c[j] = p[j]; }
        for j in coins[i-1]..amt+1 { c[j] = min(1+c[j-coins[i-1]] , p[j]); }
        for j in 0..amt+1 { p[j] = c[j];}
    }
    c[amt]
}

Thank You