Coin Change 2

LeetCode Problem #518 (Medium)

Problem Statement

You are given coins of different denominations and a total amount of money. Write a function to compute the number of combinations that make up that amount. You may assume that you have an infinite number of each kind of coin.

Testcases

Example 1:

Input: amount = 5, coins = [1, 2, 5]
Output: 4
Explanation: 
There are four ways to make up the amount:
5 = 5
5 = 2 + 2 + 1
5 = 2 + 1 + 1 + 1
5 = 1 + 1 + 1 + 1 + 1

Example 2:

Input: amount = 3, coins = [2]
Output: 0
Explanation: 
The amount of 3 cannot be made up just with coins of 2.

Example 3:

Input: amount = 10, coins = [10] 
Output: 1
Explanation:
There is only one way to make up the amount using a coin of value 10.

Problem Explanation

We are given a set of coins, each of different denominations. In this problem, we must find out the total number of unique ways to generate a particular amount of money, only using the given coins.

Each combination of coins must be distinct.

i.e. [1, 1, 2] and [2, 1, 1] cannot be considered as two different solutions since they use the same set of denominations.

Prerequisite Knowledge

Dynamic Programming

Dynamic Programming is a programming paradigm in which a large problem can be simplified by breaking it down into smaller sub-problems which yield solutions which could be used to find the final solution.

Typically, a problem can be solved using dynamic programming if it follows two prerequisite conditions:

1. Optimal Substructure—An optimal solution can be generated from the optimal solutions of its sub-problems.

2. Overlapping Subproblems—The problem can be broken down into sub-problems which can be reused multiple times.

Intuitively, we would begin to solve a dynamic programming problem by first finding its recursive solution. However, using recursion would yield an exponential time complexity which is sub-optimal for large problems.

Generally, dynamic programming follows a bottom-up approach wherein, each sub-problem must be solved at least once. For this purpose, an n-dimensional table is usually filled by solving all related sub-problems.

Memoization

This is an optimization technique that is often used in conjunction with dynamic programming wherein, a map of already computed sub-problems is maintained and the result of this problem may be utilized at further stages of the solution.

This technique uses a top-down approach since you essentially solve the "top problem" before recursively solving the sub-problems below it.

Memoization could be described as recursive dynamic programming since it is often used to implement dynamic programming.

Approach

General Approach

Consider the following example:

Change = 6
Denominations = {1, 2, 5}

In order to compute the total number of distinct ways that we can generate that amount of change from the given denominations, we must perform two actions repeatedly:

1. Calculate the number of solutions when the largest coin value is considered to be a part of the list of denominations.

2. Calculate the number of solutions when the largest coin value is removed from the list of denominations.

A solution is only considered if exact change can be produced. In this case, this means that the amount of change left at the end of the processing is 0.

If a negative value of change is obtained or there are no more coins left to process, then the solution is not considered.

At each stage of the solution, we consider a certain coin and see how it affects the total number of ways to generate the given amount.

In the tree representation, the main problem is divided into two parts to represent the actions that need to be performed as described above:

1. Left Branch: Considering the largest coin value by subtracting it from the total amount.

2. Right Branch: Not considering the largest coin value by removing it from the list of coins.

Recursive Solution

In the recursive solution, we solve for every sub-problem irrespective of whether we have seen and solved that problem before. The tree quickly becomes very large in order to accommodate the solution for every sub-problem. The solutions highlighted in green represent solutions that can be counted as a part of the final answer.

Recursion Tree for Coin Change Problem [1]

Memoization Solution

In the memoization solution, we initally begin with the same approach by dividing the main problem into two-sub problems. However, when we encounter a sub-problem that we have already solved, we simply retrieve the solution from that problem and use it in order to avoid re-computation of known sub-problems. The tree is significantly smaller in this case when compared to the recursive approach.

Memoization Tree for Coin Change Problem [2]

Source of Images:

Dynamic Programming Time Complexity - Fairly NerdyFairly Nerdy

General Formula:

table[row][col] = table[row - 1][col] + table[row][col - coins[row - 1]]

Algorithm

Top-Down DP Approach

In this approach, we use a top-down approach to break down the large problem into simpler sub-problems.

1. Initialize a one-dimensional vector to build the dynamic programming table.

2. Iterate through every coin value.

3. Build the table by adding the current value with the value at position (i - coin).

4. Return the value at the end of the array.

Time Complexity: O(n*m)

n -> amount of money

m -> denominations

Code

Optimized Solution

int change(int amount, vector<int>& coins) {
    // Initialize a vector with size (amount + 1) to account for the case of 0 coins
    vector<int> dp(amount + 1, 0);
    // Initialize the first element of the vector as 1
    dp[0] = 1;
    // Iterate through every coin value
    for(int coin : coins) {
        for(int i = coin; i <= amount; i++) {
            // Add the current value with the value obtained by moving to the position of (i - coin)
            dp[i] += dp[i - coin];
        }
    }
    // Return the last value in the array
    return dp[amount];
}