LeetCode 322: Coin Change

We can use Dynamic Programming.

Sub-problem

Say solutions[amount] represents the minimum number of coins required to change that amount.

$\text{solutions}[\text{amount}] = \min \left\{ 1 + \text{solutions}[\text{amount} - \text{coin}] : \text{coin} \in \text{coins} \text{ and } \text{coin} \le \text{amount} \right\}$

A sub-problem, solutions[amount-coin], may not be solvable and to represent that case we initialize solutions with $\infty$ except solutions[0] which has trivial solution 0.

Order

Since solutions[amount] depends on the solutions[amount-coin] and coin is positive, if we process the sub-problems in the increasing order of amount, all edges only go rightwards. So, we would have a topologically sorted order.

Time: $\mathcal{O}(|\texttt{coins}| \cdot \texttt{amount})$ , space: $\mathcal{O}(\texttt{amount})$ .

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        # We do not yet know which amount is changeable, so we start with inf.
        # Infinite number of coins means an amount does not have change.
        dp = [float('inf')] * (amount+1)
        
        # Solve trivial sub-problems
        dp[0] = 0

        for m in range(1, len(dp)):
            for c in coins:
                # No edge from sub-problem
                if c > m:
                    continue
                # func1: min
                dp[m] = min(dp[m], 1+dp[m-c])

        # func2: select last
        return dp[amount] if dp[amount] != float('inf') else -1

unreasonably effective