Dynamic Programming — ELI5

Imagine you are climbing stairs, and someone asks: “How many different ways can you climb to step 10 if you can take one or two steps at a time?”

You could try every single combination from scratch. But that would mean solving the same smaller puzzles over and over. How many ways to reach step 3? You would calculate that dozens of times while figuring out step 10.

Dynamic programming says: “Hey, if you already figured out how many ways to reach step 3, write that answer on a sticky note. Next time you need it, just look at the note instead of recalculating.”

That is the whole idea. It has two parts:

1. Break a big problem into smaller problems that overlap (the answer to step 10 depends on steps 8 and 9, which depend on steps 6 and 7, and so on).
2. Remember the answers to the small problems so you only solve each one once.

Think of it like doing a huge jigsaw puzzle. If you have already assembled one corner, you do not take it apart and redo it every time you add a new piece elsewhere. You keep what you have built and build on top of it.

Without this trick, some problems would take your computer millions of years. With it, the same problems finish in milliseconds. It is one of the most powerful ideas in all of programming.

One thing to remember: Dynamic programming is not a single formula — it is a strategy. Whenever you notice yourself solving the same sub-problem again and again, you have found a chance to use it.