🎓 A1Learner
🔍

DSA The DP Pattern

The DP pattern is a checklist of four decisions that turns a problem with repeated subproblems into a table. The four decisions are state, recurrence, order and base case.

One state, one meaning

The state ways(n) means the number of ways to reach step n. Each table entry holds exactly that count and nothing else.

ways = [1, 1]
for n in range(2, 6):
    ways.append(ways[n - 1] + ways[n - 2])
for n in range(6):
    print("ways(" + str(n) + ") =", ways[n])

A recurrence builds one answer

The recurrence for step 5 adds the counts of steps 4 and 3. Both smaller counts must exist before step 5 is computed.

ways = [1, 1, 2, 3, 5]
print("ways(4):", ways[4])
print("ways(3):", ways[3])
print("ways(5) = ways(4) + ways(3):", ways[4] + ways[3])

Base cases start the table

The base cases ways(0) and ways(1) are written directly. No recurrence is needed for either one.

ways = [0] * 6
ways[0] = 1
ways[1] = 1
print("base cases:", ways[0], ways[1])
for n in range(2, 6):
    ways[n] = ways[n - 1] + ways[n - 2]
print("filled table:", ways)

Example

def climb_table(limit):
    ways = [0] * (limit + 1)
    ways[0] = 1
    ways[1] = 1
    for n in range(2, limit + 1):
        ways[n] = ways[n - 1] + ways[n - 2]
    return ways

ways = climb_table(8)
print("state: ways(n), ways to reach step n")
print("base cases: ways(0) = 1, ways(1) = 1")
print("recurrence: ways(n) = ways(n - 1) + ways(n - 2)")
print("order: n from 2 upward")
print("table:", ways)
print("ways(8):", ways[8])

Key points

  • State: the exact meaning of one subproblem, named by its input
  • Recurrence: a rule that builds one answer from smaller answers
  • Order: the sequence that fills the table so smaller answers are ready first
  • Base case: the smallest answer, known without any smaller answer
  • The DP pattern is the four decisions state, recurrence, order and base case.
  • A wrong state makes the recurrence impossible to write.

In this example, Climbing Stairs is rebuilt by naming the four decisions first. The state is ways(n), the count of ways to reach step n. The base cases give one way to stand at step 0 and one way to reach step 1. The recurrence adds the counts of the two steps before each step. The order fills the table upward, so both smaller counts exist when needed. The finished table reaches 34 ways at step 8.

Note

Every lesson in this entry and the next one uses these same four decisions.

Try it Yourself

Edit the code, then press Run.

Running is simulated · Python Playground

Exercise

A DP table counts ways to tile a floor. Which choice names the state correctly?