Here is a confession: the first time I tried to count paths up a staircase, I made a spreadsheet. With six stairs, I had thirteen rows, a color-coding system, and two errors. There is a better way.
But before I show you the better way, I want you to feel the worse way. Really feel it. The pain of counting by hand is the exact pain that dynamic programming was invented to eliminate, and if you skip the pain, the solution will feel like magic instead of relief.
The problem: you are at the bottom of a staircase with n stairs. At each step you can move up 1 or 2 stairs. How many distinct ways can you reach the top?
A staircase. Six steps. You can take one step or two steps at a time. Before you touch any algorithm: how many distinct sequences of moves get you from the bottom to the top?
Do not calculate. Make a gut guess — write it in your head. Is it closer to 10, or closer to 100?
Most people are wrong on the first try. Not because they are bad at math — because this particular problem hides its structure behind what looks like a simple enumeration. The interesting question is not just “what is the answer” but “why does the structure make it hard to count manually, and what shape does a fast solution take?”
Let us find out. You are going to count paths yourself — first for a small staircase, then for a bigger one. What you discover during that process will drive everything that follows.