Skip to content
BENIBIX Learn

Dynamic Programming

Development🧮 Algorithms & Data StructuresAlgorithm Design Techniques

Also known as DP

Saving the answers to small parts that repeat. Each is solved once.

Think of it like

Think of it like a notebook of sums. Write each one down, so you never work it out twice.

Example

Jack works out the 50th Fibonacci number. Saving each smaller one makes 49 additions, not billions of calls.

Why it matters

Route maps, spell checkers and DNA tests all use it. Without it, those jobs would never finish.

Definition

Dynamic programming breaks a big problem into small ones that repeat. It saves each small answer. When the same small problem comes up again, it reuses the saved answer. You can save answers as you go from the top; that is called memoization. Or you can fill a table from the smallest case up. It turns many jobs that would take years into ones that take a second.

Common mistake

Using it where the small parts never repeat. Saving answers then costs memory and saves nothing.

Key takeaways

  1. 1
    Small parts repeat. That is the sign.
  2. 2
    Save each answer. Never solve twice.
  3. 3
    Top down or bottom up. Memo or table.

Compare