Coin Change

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

Example of dp.

Approach 1: Top-Down with Memoization

Remember to maintain the min_cost variable

@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

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.