Dynamic programming

Coin Change

Pinterest LinkedIn Tumblr

Coin Change is the problem of finding the number of ways of making changes for a particular amount of cents, n, using a given set of denominations d{1} dots d{m}.

source Code

package com.dsacode.Algorithm.dynamic;
 
import java.util.Arrays;
 
public class CoinChange {
    public static int[] minChange(int[] denom, int changeAmount)
    {
        int n = denom.length;
        int[] count = new int[changeAmount + 1];
        int[] from = new int[changeAmount + 1];
 
        count[0] = 1;
        for (int i = 0 ; i < changeAmount; i++)
            if (count[i] > 0)
                for (int j = 0; j < n; j++)
                {
                    int p = i + denom[j];
                    if (p <= changeAmount)
                    {
                        if (count[p] == 0 || count[p] > count[i] + 1)
                        {
                            count[p] = count[i] + 1;
                            from[p] = j;
                        }
                    }
                }
 
        if (count[changeAmount] == 0)
            return null;
 
        int[] result = new int[count[changeAmount] - 1];
        int k = changeAmount;
        while (k > 0)
        {
            result[count[k] - 2] = denom[from[k]];
            k = k - denom[from[k]];
        }
 
        return result;
    }
    public static void main(String[] args) {
        int [] arr=minChange(new int[]{1, 2, 5}, 10);
        System.out.println("General coin change that keeps track of coins: "+Arrays.toString(arr));
 
    }
 
}

Output

General coin change that keeps track of coins: [5, 5]

Algorithm Explanation

Initialize the coins denominations and sum to the utility function.
Create two arrays with change amount and iterate the array till change amount and find the coin change solution.
Use dynamic programming to cache the results for sub problems.
Return the coin change solution and print the result.

Time Complexity

Best CaseAverage CaseWorst Case
O(mn)

Reference

  1. http://interactivepython.org/runestone/static/pythonds/Recursion/DynamicProgramming.html
  2. http://www.columbia.edu/~cs2035/courses/csor4231.F07/dynamic.pdf
  3. http://www.ccs.neu.edu/home/jaa/CS7800.12F/Information/Handouts/dyn_prog.pdf
  4. https://www.cs.usfca.edu/~galles/visualization/DPChange.html

Write A Comment