CoinChangeMin.java

/*
    Problem: Given denominators (coins) and an amount,
    find minimum number of coins to make the amount.

 */
public class CoinChangeMin {
    // complexity: time exponential
    static int findMinCoinsRecur(int[] coins, int n, int S) {
        // base case, amount = 0
        if (S == 0) {
            return 0;
        }
        int result = Integer.MAX_VALUE;
        for (int i=0; i<n; i++) {
            if (coins[i] <= S) {
                int temp = findMinCoinsRecur(coins, n, S-coins[i]);
                if (temp != Integer.MAX_VALUE &&
                        temp + 1 < result) {
                    result = temp + 1;
                }
            }
        }
        return result;
    }

    // complexity: time O(n*m), space O(m), n: number of coins, m: sum
    static int findMinCoins(int[] coins, int S) {
        int[] memo = new int[S + 1];
        // initialize
        for (int i=1; i<memo.length; i++) { memo[i] = Integer.MAX_VALUE; }
        for (int i=1; i<=S; i++) {
            for (int j=0; j<coins.length; j++) {
                if (coins[j] <= i && (memo[i-coins[j]] + 1 < memo[i])) {
                    memo[i] = memo[i-coins[j]] + 1;
                }
            }
        }
        return memo[S];
    }

    public static void main(String[] args) {
        int[] coins = {1, 3, 5};
        int S = 11;
        System.out.println(findMinCoinsRecur(coins, coins.length, S));
        System.out.println(findMinCoins(coins, S));
    }
}

/*
References:
http://algorithms.tutorialhorizon.com/dynamic-programming-minimum-coin-change-problem/
http://www.geeksforgeeks.org/find-minimum-number-of-coins-that-make-a-change/
http://www.programcreek.com/2015/04/leetcode-coin-change-java/
*/