Lesson 6 of 16

Remember Results with Dynamic Programming

Find the minimum number of coins needed to make 6 using denominations 1, 3, and 4. Greedy chose three coins, but two suffice. Remembering optimal answers for smaller amounts lets us compare every possible last coin.

Write three things first

• State: dp[x] is the minimum number of coins needed for amount x.
• Base case: dp[0] = 0; no coins are needed for zero.
• Recurrence: If the last coin is c, the candidate is dp[x-c] + 1. Minimize across eligible denominations.

Fill amounts from smallest upward so earlier answers are ready. Leave impossible amounts at infinity. Assume positive integer denominations with unlimited copies of each coin.

coins = [1, 3, 4]
amount = 6
dp = [float("inf")] * (amount + 1)
dp[0] = 0
for value in range(1, amount + 1):
    for coin in coins:
        if coin <= value:
            dp[value] = min(dp[value], dp[value - coin] + 1)
print(dp[amount])

The output is 2. For amount 6, candidates are dp[5]+1, dp[3]+1, and dp[2]+1. The smallest is dp[3]+1 = 2.

How does this relate to recursion?

Dynamic programming (DP) describes a design that avoids recomputing identical states, not a particular syntax. Memoization stores answers as recursive calls need them; tabulation fills a table from smaller states. The example uses tabulation.

The subproblems must support construction of an optimal answer, and repeated states must allow reuse. Recursion alone does not automatically yield efficient DP.

For target amount A and k denominations, time is O(Ak) and space is O(A). A very large amount makes the table expensive.

Check your understanding

With only coins 2 and 4, how should amount 3 be represented? What fails if dp[0] starts at infinity?