LeetCode 322. Coin Change

Question: https://leetcode.com/problems/coin-change/

Given a list of coins, and the amount that we want to spend, what is the minimum number of coins that you can use to make up for that amount? This is a very classic dynamic programming problem. For any dynamic programming problem, there are two approaches: top-down and bottom-up. Either approach is fine, but in general, top-down is easier to reason about.

In any dynamic programming problem, the main difficulty is in framing the question to find the sub-problems that can lead to the complete solution. Fortunately for this question, the framing is quite obvious. Let F(x) be the function that yields the minium # of coins needed to make up for the amount x. Let [c1, c2, ...cn] be the coins available. To know the minimum # of coins needed for the amount x, we just need to know the min # of coins needed for x-c1, x-c2, x-c3 and so on, and find among these the minium # of coins, and finally, we will add 1 to it to get the solution. Formally, the dynamic programming problem as stated as:

 \begin{equation*} F(x) =(\underset{i \in n} {\text{min}} F(x-c_i)) + 1 \end{equation*}

The base case is the recursion is F(coin) = 1 for all coins available since any given amount = coin value will only require 1 coin. Furthermore, F(0) = 0, since there is simply no way to get amount = 0. After all, we have no 0-value coin! The following solution implements the top-down approach using recursion and memoization by initializing the mem array to store the solutions up to amount.

class Solution(object):
    def coinChange(self, coins, amount):
        """
        :type coins: List[int]
        :type amount: int
        :rtype: int
        """
        mem = [0 for i in range(amount+1)]
        def helper(amount):
            if amount == 0:
                return 0
            if amount<0:
                return -1
            if amount in coins:
                return 1
            if mem[amount]!=0:
                return mem[amount]

            minChange = float('inf')
            for coin in coins:
                change = self.coinChange(coins, amount-coin)
                if change>0 and change < minChange:
                    minChange = change +1

            if minChange == float("inf"):
                return -1
            else:
                return minChange
        
        return helper(amount)

Now, this code wouldn't pass leetcode's tests. I am pretty sure the solution is correct. It's just that the mem implementation might need to be changed to a dictionary in order for it to pass. However, I will be focusing on the bottom-up solution because most of the time, this approach will be more efficient and require a little bit more thinking. Unlike the top-down solution, the bottom-up solution builds up the solution from the base cases. Just like the mem array before, dp will be the array that we store our solutions to different amounts. We will initialize it to be all +inf except for amount=0 where we set dp[0]=0 because we want the minimum when we do the comparison, and setting initial value to +inf will force an update to a number. Essentially, we are building up the solution to amount starting from amount=1 (due to the 0 counting convention in most programming language, we are actually building up to amount+1). The good thing about building from bottom-up is that we are guaranteed that we will have what we need to compute for amount=x because the comparisons we need are already computed previously! For each amount, we simply apply the definition for each coin and find the minimum # of coins needed among all subproblems. The only caveat is when we exit the loop, we need to check if dp[amount]>amount. If this condition is met it implies that no solution can be found. Notice that when no combination can be found. dp[amount] would not be updated and will remain to be +inf. In general, any amount that has no solution will remain to be +inf because one of their sub-solutions will not be updated at all (i.e. for some sub-solution i, coin <=i will be true for all coin) rendering no update to dp[i].

class Solution(object):
    def coinChange(self, coins, amount):
        """
        :type coins: List[int]
        :type amount: int
        :rtype: int
        """
        maxNum = amount + 1
        dp = [float("inf") for _ in range(maxNum)]
        dp[0] = 0
        for i in range(1, maxNum):
            for j, coin in enumerate(coins):
                if (coin <= i):
                    dp[i] = min(dp[i], dp[i-coin]+1)
        if dp[amount] > amount:
            return -1
        else:
            return dp[amount]