# Coin Change https://leetcode.com/problems/coin-change/ Example of [[dp]]. ## Approach 1: Top-Down with Memoization Remember to maintain the `min_cost` variable ```python @lru_cache(None) def dfs(rem): if rem < 0: return -1 if rem == 0: return 0 min_cost = float('inf') for coin in coins: res = dfs(rem - coin) if res != -1: min_cost = min(min_cost, res + 1) return min_cost if min_cost != float('inf') else -1 return dfs(amount) ``` Time complexity: $O(Sn)$, where $S$ is the amount and $n$ is the count of denominations. In worst case the recursion tree has height of $S$ (reduce `rem` by `1` at a time), and we need `n` iterations for each of the subproblems. Space complexity: $O(S)$. ## Approach 2: Bottom Up ```python dp = [float('inf')] * (amount + 1) dp[0] = 0 for coin in coins: for x in range(coin, amount + 1): dp[x] = min(dp[x], dp[x - coin] + 1) return dp[amount] if dp[amount] != float('inf') else -1 ``` Use `float('inf')` to mark `dp[x]` as no feasible combinations. Putting `coin` in the outer loop makes the algorithm more efficient, and notice that, since `x` starts with `coin`, we know that `dp[x - coin] = dp[coin - coin] = 0` is well defined. Thus ensure that we're always working on valid base cases.