🎓 A1Learner
🔍
0 of 47 lessons completed

Recognizing a DP Problem

Recognizing a DP problem is the skill of spotting that a problem is solved from smaller answers of itself. The signals are choices at each step and a question about a count, a minimum, or a maximum.

The recognition signal

Three signals together mark a DP problem. The checklist below names them in plain words.

signals = [
    "Choices are made one step at a time.",
    "The question asks for a count, a minimum, or a maximum.",
    "A smaller version of the problem appears inside the larger one.",
]
for s in signals:
    print("Signal: " + s)

The recognition template

The test below checks both signals at once. Climbing stairs passes both, while finding the middle of a list passes neither.

def looks_like_dp(smaller_copies, asks_count_min_max):
    return smaller_copies and asks_count_min_max


print("Climbing stairs:", looks_like_dp(True, True))
print("Middle of a list:", looks_like_dp(False, False))

Worked problem: ways to make 5

Making 5 from coins 1, 2, and 5 is a count built from smaller amounts. A table over the coins gives four ways.

coins = [1, 2, 5]
ways = [0] * 6
ways[0] = 1
for coin in coins:
    for amount in range(coin, 6):
        ways[amount] += ways[amount - coin]
print("Ways to make 5:", ways[5])

Example

coins = [1, 5, 10]
big = 99
fewest = [big] * 12
fewest[0] = 0
for amount in range(1, 12):
    for coin in coins:
        if coin <= amount:
            fewest[amount] = min(fewest[amount], fewest[amount - coin] + 1)
print("Fewest coins for 11:", fewest[11])

Key points

  • A DP problem asks for a count, a minimum, or a maximum built from smaller answers.
  • Use the signals of step-by-step choices and smaller copies to test a problem.
  • Find the recurrence first, then choose memoization or tabulation to compute it.
  • Recognizing a DP problem means matching its shape before writing any solution code.

Making 11 is a minimum built from smaller amounts. Each amount tries every coin and keeps the smallest count found. The answer is 2, from one 10 coin and one 1 coin.

Note

a problem with no smaller copies of itself is not a DP problem.

Try it Yourself

Edit the code, then press Run.

Running is simulated · Python Playground

Exercise

Which problem is most likely a DP problem?