Sometimes a big problem asks the same small question again and again. Dynamic programming says: save the answer the first time, then reuse it.
It is like building a puzzle and keeping finished pieces in trays. When you need one again, you pick it up instead of rebuilding it.
A frog on the stairs
A frog can jump one stair or two stairs. How many ways can it reach stair 4? To reach stair 4, its last jump came from stair 3 or stair 2. So we need the answers for stairs 3 and 2.
Those smaller questions also ask about earlier stairs. Without saving answers, we solve the same little stair problems many times.
Two friendly styles
Memoization starts with the big question and uses recursion. Whenever it solves a small question, it saves the answer in a table.
Tabulation starts with the smallest answers and fills a table from the bottom up. For the frog, we find stair 1, then stair 2, then stair 3, until we reach stair 4.
- Break the problem into smaller problems.
- Notice which small problems repeat.
- Save each answer once.
- Build or return the big answer from saved answers.
When this idea helps
Dynamic programming works well when small problems repeat and their answers can combine into a larger answer. It appears in route planning, text comparison, scheduling, and many puzzle problems.
It does not fit every problem. First look for repeated work. If nothing repeats, saving answers may only add clutter.
def ways_to_climb(stairs):
saved = [1, 1]
for stair in range(2, stairs + 1):
next_answer = saved[-1] + saved[-2]
saved.append(next_answer)
return saved[stairs]
print(ways_to_climb(4)) # 5 waysYour tiny challenge
Write the ways to reach stairs 1, 2, 3, and 4. Keep every answer on a card. Each new card can use the two cards before it. That little table is dynamic programming.