518. Coin Change 2

Here is my discussion post.

It is challenge to find all possible coin change and also avoid duplication. How to remove duplication? I like to do a case study on example 5, coins = [1, 2, 5] and then figure out how to do the work.

Case study 5, [1, 2, 5]
I like to work on example, amount = 5, coins = [1, 2, 5], all coin changes are the following 4 groups,
5 = 5
5 = 2 + 2 + 1
5 = 2 + 1 + 1 + 1
5 = 1 + 1 + 1 + 1 + 1

The reason I like to case studay the example because I studied one of solution using dynamic programming and memoization technique.

First, sort all coins in ascending order, so coins = [1, 2, 5].
Now we like to brute force all possible solutions for minimum coin value.
There are three cases, minimum coin is 1, or 2, or 5.

For each case, we like to solve the problem using subproblem,
5 = 5
5 = 2 + 2 + 1
5 = 2 + 1 + 1 + 1
5 = 1 + 1 + 1 + 1 + 1

Minimum coin value

The above four group can be put into two groups; one is minimum coin value is 1, the second one is minimm coin value 5.
The minimum coin value is 1:
5 = 1 + 1 + 1 + 1 + 1
5 = 1 + 1 + 1 + 2
5 = 1 + 2 + 2

The minimum coin value is 5:
5 = 5

In order to solve the problem, I have to memorize two things, first is to brute force all minimum coin value in ascending order; inner loop is to exhaust all possible count of minimum coin used in the coin change.
minimum coin value has three options, 1, 2, 5.
For the minimum coin value = 1, there are five options, 1, 2, 3, 4, 5 of coin value = 1;

Subproblem definition
Amount = 5, Coins = [1, 2, 5]
F(Amount, Index)
Case 1: minimum coin is 5, index = 2
We only can use coin 5 to make value 5, so
F(0, 2) = 0
F(1, 2) = 0
F(2, 2) = 0
F(3, 2) = 0
F(4, 2) = 0
F(5, 2) = 1

Case 2 : minimum coin is 2, index = 1
F(0, 1) = 0
F(1, 1) = 0, the result is 2
F(2, 1) = 1
F(3, 1) = 0
F(4, 1) = 1, the result is 2 + 2
F(5, 1) = 0

Case 1: minimum coin is 1, index = 0

The idea is to use combinatorics knowledge to solve it first, and then translate the idea into C# code.

To avoid duplicated calculation, we like to define the subproblem F(amount, index), amount is the sum, index is the index of coin array.

Here is the code I chose to study. I like to write some study notes to help me learn the algorithm quickly.

public class Solution {
    /// <summary>
        /// June 20, 2019
        /// study code 
        /// https://leetcode.com/problems/coin-change-2/discuss/99239/C-DFS-with-memorization-of-course-DP-is-better
        /// </summary>
        /// <param name="amount"></param>
        /// <param name="coins"></param>
        /// <returns></returns>
        public int Change(int amount, int[] coins)
        {
            // order coins in order to prune recursion
            Array.Sort(coins);

            // init memorization to -1 (unvisited)
            var map = new int[amount + 1, coins.Length];

            for (int i = 0; i < map.GetLength(0); i++)
            {
                for (int j = 0; j < map.GetLength(1); j++)
                {
                    map[i, j] = -1;
                }
            }

            // DFS
            return CountUsingDepthFirstSearch(coins, amount, 0, map);
        }

        /// <summary>
        /// depth first search
        /// </summary>
        /// <param name="coins"></param>
        /// <param name="amount"></param>
        /// <param name="index"></param>
        /// <param name="map"></param>
        /// <returns></returns>
        private int CountUsingDepthFirstSearch(int[] coins, int amount, int index, int[,] map)
        {
            if (amount == 0)
            {
                return 1;
            }

            if (index == coins.Length)
            {
                return 0;
            }

            if (map[amount, index] != -1)
            {
                return map[amount, index];
            }

            int count = 0;
            for (int i = index; i < coins.Length; i++)
            {
                if (coins[i] > amount) break;

                // using this coin as many times as possible before going to next coin
                int times = 1;
                while (times * coins[i] <= amount)
                {
                    var nextAmont = amount - times * coins[i];
                    count += CountUsingDepthFirstSearch(coins, nextAmont, i + 1, map);
                    times++;
                }
            }

            // memorize
            map[amount, index] = count;
            return count;
        }
}