Coin Change: Recursive DP

First Thoughts

To find the minimum number of coins, best to start with the largest amount of coin and "use up" the amount remaining. However, this was not an ideal way, because some coin values needed to be tested for all available coin types. Instead, the main logic needed is forming an array of size [amount] and accessing the minimum amount of coins by array[amount-1]. The array is initialized to zero, and -1 if the amount is negative number. Can have different combinations of forming based on what last coin we use, so need to try out for each available coin type, and take the smallest one.

Ideal Recursive Solution

class Solution {
	public int coinChange(int[] coins, int amount) {
    	return doWork(coins, amount, new int[amount]);
    }
    
    private int doWork(int[] coins, int rem, int[] minCounts) {
    	if (rem < 0) return -1;
        if (rem == 0) return 0;
        if (minCounts[rem-1] != 0) return minCounts[rem-1];
        
        int min = Integer.MAX_VALUE;
        for (int coin : coins) {
        	int prevCount = doWork(coins, rem-coin, minCounts);
            if (prevCount!=-1 && prevCount < min) min = prevCount+1;
        }
        if (min == Integer.MAX_VALUE) minCounts[rem-1] = -1;
        else minCounts[rem-1] = min;
        
        return minCounts[rem-1];
    }
}

Catch Point

• Think about how we reach the solution. If we know the penultimate minimum coin count, we can add one (where the last coin just simply fills up the remaining value) to that count and that should still be the minimum count.

• If amount-coin goes into negative range, this means it cannot be formed (thus the base check of rem < 0

• If and only if amount-coin reaches exactly 0 does it mean the counting process is completed

• It is important to avoid re-calculations of minimun coin counts -> thus the need for minCounts array (and use it if already calculated before)