Problem_3_Coin_Change.java

package Dynamic_Programming.Unbounded_Knapsack;

// Problem Statement: Coin Change
// LeetCode Question: 518. Coin Change II

public class Problem_3_Coin_Change {
    // Brute Force
    class Solution_1 {

        public int countChange(int[] denominations, int total) {
            return this.countChangeRecursive(denominations, total, 0);
        }

        private int countChangeRecursive(int[] denominations, int total, int currentIndex) {
            // basic checks
            if (total == 0)
                return 1;

            if(denominations.length == 0 || currentIndex >= denominations.length)
                return 0;

            // recursive call after selecting the coin at the currentIndex
            // if the coin at currentIndex exceeds the total, we shouldn't process this
            int sum1 = 0;
            if( denominations[currentIndex] <= total )
                sum1 = countChangeRecursive(denominations, total - denominations[currentIndex], currentIndex);

            // recursive call after excluding the coin at the currentIndex
            int sum2 = countChangeRecursive(denominations, total, currentIndex + 1);

            return sum1 + sum2;
        }

    }

    // Top-down Dynamic Programming with Memoization
    class Solution_2 {

        public int countChange(int[] denominations, int total)

        {
            Integer[][] dp = new Integer[denominations.length][total + 1];
            return this.countChangeRecursive(dp, denominations, total, 0);
        }

        private int countChangeRecursive(Integer[][] dp, int[] denominations, int
                total, int currentIndex)

        {
            // base checks
            if (total == 0)
                return 1;

            if(denominations.length == 0 || currentIndex >= denominations.length)
                return 0;

            // if we have already processed a similar sub-problem, return the result from memory
            if(dp[currentIndex][total] != null)
                return dp[currentIndex][total];

            // recursive call after selecting the coin at the currentIndex
            // if the number at currentIndex exceeds the total, we shouldn't process this
            int sum1 = 0;
            if( denominations[currentIndex] <= total )
                sum1 = countChangeRecursive(dp, denominations, total - denominations[currentIndex], currentIndex);

            // recursive call after excluding the number at the currentIndex
            int sum2 = countChangeRecursive(dp, denominations, total, currentIndex + 1);

            dp[currentIndex][total] = sum1 + sum2;
            return dp[currentIndex][total];
        }

    }
    // Bottom-up Dynamic Programming
    class Solution_3 {

        public int countChange(int[] denominations, int total) {
            int n = denominations.length;
            int[][] dp = new int[n][total + 1];

            // populate the total=0 columns, as we will always have an empty set for zero total
            for(int i=0; i < n; i++)
                dp[i][0] = 1;

            // process all sub-arrays for all capacities
            for(int i=0; i < n; i++) {
                for(int t=1; t <= total; t++) {
                    if(i > 0)
                        dp[i][t] = dp[i-1][t];
                    if(t >= denominations[i])
                        dp[i][t] += dp[i][t-denominations[i]];
                }
            }

            // total combinations will be at the bottom-right corner.
            return dp[n-1][total];
        }

    }

}