🎓 A1Learner
🔍
0 of 47 lessons completed

Practice: DP Problems

Practice with dynamic programming problems is work on problems that break into overlapping smaller problems. It turns the recurrence and table methods from earlier lessons into speed and accuracy under time pressure.

Spot a dynamic programming problem

The question asks for a count, a best value, or a yes-or-no answer over many choices. The same smaller problem appears again and again inside larger ones.

print("Solve 4 needs 3 and 2")
print("Solve 3 needs 2 and 1")
print("Solve 2 appears twice")

The tabulation template

Tabulation fills a table of smaller answers in order. Each new entry reads only entries that are already filled.

def count_ways(n):
    table = [0] * (n + 1)
    table[0] = 1
    if n >= 1:
        table[1] = 1
    for step in range(2, n + 1):
        table[step] = table[step - 1] + table[step - 2]
    return table[n]

print("Ways for 5 steps:", count_ways(5))

Worked problem: climb with memory

Memoization stores each smaller answer the first time it is computed. Later calls read the stored answer instead of computing it again.

memo = {}

def count_ways(n):
    if n <= 1:
        return 1
    if n not in memo:
        memo[n] = count_ways(n - 1) + count_ways(n - 2)
    return memo[n]

print("Ways for 6 steps:", count_ways(6))

Example

def fewest_coins(coins, amount):
    table = [999] * (amount + 1)
    table[0] = 0
    for total in range(1, amount + 1):
        for coin in coins:
            if coin <= total:
                table[total] = min(table[total], table[total - coin] + 1)
    return table[amount]

print("Fewest coins for 6:", fewest_coins([1, 3, 4], 6))

Key points

  • Dynamic programming is a method for problems that repeat the same smaller problems.
  • Use a recurrence to state how a larger answer is built from smaller answers.
  • Use memoization to store a smaller answer the first time it is computed.
  • Use tabulation to fill a table of smaller answers from the bottom up.

The table holds the fewest coins for every smaller amount. Each amount tries every coin and keeps the best total. The answer for 6 uses two coins of 3.

Note

a problem fits this method when smaller answers are reused, not computed once and thrown away.

Try it Yourself

Edit the code, then press Run.

Running is simulated · Python Playground

Exercise

A problem asks for the fewest coins to make an amount, and smaller amounts are reused many times. Which method fits best?