Dynamic Programming: Start by Defining the State

By Hourly DSA · September 29, 2026 · 4 min read

Dynamic programming stores answers to smaller subproblems so you don't solve the same ones repeatedly. The most useful first step is defining what one stored answer means. Once that's precise, the recurrence and base cases have something solid to refer to.

Start with a counting problem small enough to solve by hand.

Count ways to climb four stairs

You may move up one or two stairs at a time. How many sequences of moves reach stair four, starting at stair zero?

There are five:

1 + 1 + 1 + 1
1 + 1 + 2
1 + 2 + 1
2 + 1 + 1
2 + 2

Order matters here. Taking one stair and then two is a different sequence from taking two and then one. If the problem counted combinations without regard to order, this would be a different task.

Before choosing an algorithm, settle what counts as a distinct answer.

Give the state a sentence

Let ways[i] mean the number of move sequences that reach stair i.

That's the state definition. It tells you exactly what belongs at each position and what the final answer should be: ways[n].

A vague definition like “the answer at i” isn't enough. For a different problem, i might represent moves used, cost spent, or items considered. Those meanings lead to different transitions.

Derive the recurrence from the last move

Every sequence reaching stair i ends with either:

A one-stair move from i − 1.
A two-stair move from i − 2.

The two groups don't overlap because their last moves differ. They also cover every allowed way to arrive. So:

ways[i] = ways[i - 1] + ways[i - 2]

You add counts because you're counting alternative sequences. In a minimum-cost problem, you might instead take a minimum. Choose the operation from the meaning of the answer, not from a memorized template.

Base cases are part of the model

Set ways[0] = 1: there is one sequence of moves that stays at the starting position, the empty sequence.

Set ways[1] = 1: one single-stair move reaches stair one.

Then fill the rest:

Stair i	Ways to reach it	Reason
0	1	Empty sequence
1	1	One single move
2	2	1 + 1
3	3	2 + 1
4	5	3 + 2

The numbers in the final column refer to counts from earlier states, not stair sizes.

Defining ways[0] as zero would lose the direct two-stair path when computing ways[2]. A base case should match the story your state tells.

Where repeated work appears

A plain recursive solution for ways[4] asks for ways[3] and ways[2]. Computing ways[3] asks for ways[2] again. As n grows, those repeated branches multiply.

Memoization stores each recursive answer after computing it. Tabulation fills answers in an order that makes their dependencies available. Both can compute these n + 1 states in O(n) arithmetic operations.

For this problem, you only need the previous two counts to compute the next one. Keeping two rolling values reduces auxiliary storage from O(n) entries to O(1) entries.

Those familiar complexity claims assume fixed-cost arithmetic and values that fit in the numeric representation. Exact counts grow with n; arbitrary-precision arithmetic introduces a separate cost for larger numbers.

How to recognize a useful DP state

Look for a subproblem you can describe without needing its full history. If two different paths reach the same state, can they share the answer from that point onward?

Sometimes an index is enough. Sometimes you need more information, such as an index and remaining capacity. If future choices depend on something you left out, the state is incomplete.

Ask:

What does this stored value mean?
What smaller values determine it?
Why do those possibilities cover every valid answer?
Which states are known without recursion?

A quick variation

What if you can move one or three stairs at a time?

The transition becomes ways[i] = ways[i - 1] + ways[i - 3], treating negative indices as zero ways and retaining ways[0] = 1. You changed the possible last moves, so the recurrence changed with them.

Hourly DSA gives you a compact way to practice reasoning through changes like this. If a problem still feels too large, use the steps in what to do when you're stuck to find a smaller case and a clearer state.