Coin Change Problem

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

Introduction

Coin change is another classical Dynamic Programming problem.

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

You have to tell in how many ways you can form the given amount by using these coins any number of times.

For Example : If coins are [1, 2, 3] and the amount is 4, there are 4 ways to form the amount using the coins, that is,

4 = 1 + 1 + 1 + 1
4 = 1 + 1 + 2
4 = 1 + 3
4 = 2 + 2

Hence, the output should be 4.

Similarly, if the coins are [1, 3] and the amount is 4, there are 2 ways only.

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 sum of both the cases.

If amount is 0, there is only 1 way to form the amount, that is, by not using any coin.

Also, if n is 0 and amount is not 0, we have to return 0, because there are no ways to make the amount in this way.

Function

Here is the function using above algorithm

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

    // If amount is 0, there is one way of making the change
    // That is, do not take any coin
    if amount == 0 { return 1; }

    // If no coins left, return 0
    if n==0 { return 0; }

    // 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 coin_change(coins, amount, n-1);
    }

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

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

With driver code

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

    // If amount is 0, there is one way of making the change
    // That is, do not take any coin
    if amount == 0 { return 1; }

    // If no coins left, return 0
    if n==0 { return 0; }

    // 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 coin_change(coins, amount, n-1);
    }

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

    // Return sum of both cases.
    return coin_change(coins, amount, n-1)+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];
    println!("{}", coin_change(&coins, amount, coins.len()));
}

Input

1 2 3
4

Output

4

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 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 1 and if n is 0 and amount > 0, return 0.
Else, use recursive logic to calculate the given value and store it in the DP matrix.

Function

Here is the function using above algorithm

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

    // If amount is 0, there is one way of making the change
    // That is, do not take any coin
    if amount == 0 { return 1; }

    // If no coins left, return 0
    if n==0 { return 0; }

    // 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(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 coin_change of n-1 items
    // If include, answer would be reduce the amount by denomination
    // And calculate the coin_change of n items.
    // Because we can include the coin again

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

With driver code

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

    // If amount is 0, there is one way of making the change
    // That is, do not take any coin
    if amount == 0 { return 1; }

    // If no coins left, return 0
    if n==0 { return 0; }

    // 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(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 coin_change of n-1 items
    // If include, answer would be reduce the amount by denomination
    // And calculate the coin_change of n items.
    // Because we can include the coin again

    // Return sum of both cases.
    dp[n][amount] = Option::from( coin_change(coins, amount, n-1, dp)+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];

    println!("{}", coin_change(&coins, amount, coins.len(), &mut dp));
}

Input

1 2 3
4

Output

4

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 0, because if n == 0, we can not make amount, except when amount = 0. Also, set first column as 1, because if amount is 0, there is always 1 way to produce this.
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 dp[i][amount-coins[n-1]] + dp[i-1][amount] for inclusion and exclusion of the given coin respectively.
Return the dp[n][amount] as the final answer.

Function

Here is the function using above algorithm

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

    // Set first column as 1
    for i in 0..n+1 { dp[i][0] = 1; }

    // Set the first row as 0
    for i in 1..amount+1 { dp[0][i] = 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..coins[i-1]{
            dp[i][j] = dp[i-1][j];
        }

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

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

With Driver code

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

    // Set first column as 1
    for i in 0..n+1 { dp[i][0] = 1; }

    // Set the first row as 0
    for i in 1..amount+1 { dp[0][i] = 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..coins[i-1]{
            dp[i][j] = dp[i-1][j];
        }

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

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


// 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![0 as usize; amount+1 ]; coins.len()+1];

    println!("{}", coin_change(&coins, amount, coins.len(), &mut dp));
}

Input

1 2 3
4

Output

4

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 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.

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

    let mut prev = vec![0; amount+1];
    let mut current = vec![0; amount+1];

    // Set first column to 1
    prev[0] = 1;
    current[0] = 1;

    // 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..coins[i-1]{
            current[j] = prev[j];
        }

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

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

    // Return last element of current array
    current[amount]
}

Use the same driver code except removing the dp matrix input.

Input

1 2 3
4

Output

4

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

Conclusion

Coin Change Problem is a classical Dynamic Programming problem. In this problem, you have to tell in how many ways you can form the given amount by using given coins any number of times.

In this article, we saw how to solve the 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

fn coin_change(coins:&Vec<usize>, amount : usize, n:usize) -> usize{
    let mut prev = vec![0; amount+1];
    let mut current = vec![0; amount+1];
    prev[0] = 1; current[0] = 1;
    for i in 1..n+1 {
        for j in 1..coins[i-1]{ current[j] = prev[j]; }
        for j in coins[i-1]..amount+1 { current[j] = current[j-coins[i-1]] + prev[j]; }
        for j in 0..amount+1 { prev[j] = current[j]; }
    }
    current[amount]
}

Thank You