How would you implement the coin change problem using dynamic programming?

The coin change problem is a problem of finding the number of ways of making changes for a particular amount of money using coins of given denominations.

We can solve this problem using dynamic programming by creating a solution array to keep track of the solutions for the problems. Let’s assume that our given coin denominations are d[0], d[1], ..., d[m-1].

Let’s define an array dp[], where dp[i] will be storing the number of solutions for value i. We need m+1 rows as in the bottom-up approach, dp[i] will be computed using the solution to previous i values.

Here is the iterative approach using dynamic programming:

Define dp[N+1] where N is the amount you are making change for. dp[i] will be storing the number of solutions for value i.

Algorithm pseudo code:

def coinChange(coins, amount):
    # Initialize dp array
    dp = [0]*(amount+1)

    # Base case: There is exactly 1 way to create a sum of 0, that is using no coin
    dp[0] = 1

    # Iterate over all coins
    for i in range(0, len(coins)):
        # Compute the number of ways for all values
        # greater than the coin value
        for j in range(coins[i], amount+1):
            dp[j] += dp[j - coins[i]]
    
    # Return the number of ways to make the amount using coins
    return dp[amount]

This dynamic programming solution has O(mN) time complexity as each subproblem takes O(1) time to solve, where m is the array length and N is the amount.

You can visualize this process in a matrix as follows:

$$\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|} \hline \text{dp} & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ \hline 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 2 & 1 & 1 & 2 & 2 & 3 & 3 & 4 & 4 & 5 & 5 & 6 \\ 5 & 1 & 1 & 2 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 10 \\ \hline \end{array}$$
For example, the number of ways to make change for 10 using coin denominations [1, 2, 5] is 10.