DSA What Is Dynamic Programming
Dynamic programming is a method that solves each smaller subproblem once and stores its answer. A subproblem is a smaller version of the same problem.
Naive Fibonacci repeats work
A counter records every call the naive function makes. Reaching fib(10) already takes 177 calls.
calls = 0
def fib(n):
global calls
calls += 1
if n < 2:
return n
return fib(n - 1) + fib(n - 2)
print(fib(10))
print("calls:", calls)Memoised Fibonacci answers once
The memo table stores each answer after its first computation. Later calls read the stored answer instead of recomputing it.
calls = 0
memo = {}
def fib(n):
global calls
calls += 1
if n in memo:
return memo[n]
if n < 2:
return n
memo[n] = fib(n - 1) + fib(n - 2)
return memo[n]
print(fib(10))
print("calls:", calls)A table builds upward
The table method fills answers from fib(0) upward. Each new entry adds the two entries before it.
table = [0, 1]
for n in range(2, 11):
table.append(table[n - 1] + table[n - 2])
print(table)Example
def fib_naive(n, counter):
counter[0] += 1
if n < 2:
return n
return fib_naive(n - 1, counter) + fib_naive(n - 2, counter)
def fib_memo(n, counter, memo):
counter[0] += 1
if n in memo:
return memo[n]
if n < 2:
return n
memo[n] = fib_memo(n - 1, counter, memo) + fib_memo(n - 2, counter, memo)
return memo[n]
def fib_table(n):
table = [0, 1]
additions = 0
for i in range(2, n + 1):
table.append(table[i - 1] + table[i - 2])
additions += 1
return table[n], additions
n = 25
c1 = [0]
print("naive:", fib_naive(n, c1), "calls:", c1[0])
c2 = [0]
print("memoised:", fib_memo(n, c2, {}), "calls:", c2[0])
answer, additions = fib_table(n)
print("table:", answer, "additions:", additions)Key points
- Dynamic programming: solving each subproblem once and storing its answer
- Subproblem: a smaller version of the same problem
- Overlapping subproblems: subproblems that a naive solution computes again and again
- Memoisation: storing a function's answers in a table it checks before computing
- Table method: building the answers from the smallest subproblem upward
- Storing answers only helps when subproblems repeat.
In this example, three methods compute fib(25) and count their own work. The naive method makes 242785 calls because it recomputes the same subproblems. The memoised method makes 49 calls because each distinct subproblem is computed once. The table method makes 24 additions, one per new entry from fib(2) to fib(25). All three print the same answer, 75025. Only the repeated work differs, and the counters prove it.
Note
A problem with no repeats gains nothing from a table.
Try it Yourself
Edit the code, then press Run.
Running is simulated · Python Playground
Exercise
What does memoisation store so that repeated work disappears?