Dynamic Programming: Where to Start If It Feels Impossible

Dynamic programming feels impossible because people start by trying to fill out tables instead of writing plain functions. If you cannot write a recursive solution that solves a problem correctly, you have no business touching a DP table.

The Sequence: Recursion to Memoization to DP

Every dynamic programming problem is just a recursive function that repeats itself. To see this clearly, look at the classic problem of climbing stairs where you can take 1 or 2 steps to reach the top.

Write the recursive function first. If you are at step $n$, you arrived from either step $n-1$ or step $n-2$. Therefore, the total number of ways to reach step $n$ is the sum of the ways to reach step $n-1$ and step $n-2$. In code, ways(n) = ways(n-1) + ways(n-2).

Plain recursion recalculates the exact same subproblems thousands of times. If you draw the tree for ways(5), you will compute ways(2) eight separate times.

Memoization is just adding a cache to your recursion. Before computing any value, check if you already calculated it. If it is in your array or map, return it immediately. The recurrence stays identical to the pure recursive version, but the execution time drops from exponential to linear.

Converting a memoized solution into an iterative table requires flipping the direction of execution. Instead of starting at $n$ and working down to the base cases, start at the base cases and build up to $n$. For climbing stairs, a loop from $2$ to $n$ filling an array dp[i] = dp[i-1] + dp[i-2] is the exact same logic as the memoized function, just running in reverse order.

The Ladder: Fibonacci, Stairs, and House Robber

Master this specific progression: Fibonacci, Climbing Stairs, and House Robber.

Fibonacci defines the base recurrence: F(n) = F(n-1) + F(n-2). It has no constraints other than the sequence itself.

Climbing stairs is identical to Fibonacci with a slight shift in the base cases.

House Robber introduces a choice and a state constraint: you cannot rob two adjacent houses. The recurrence changes because at every house, you choose between robbing the current house plus the loot from two houses ago, or skipping the current house and keeping the loot from the previous house. In words: max_loot(i) = max(loot[i] + max_loot(i-2), max_loot(i-1)).

Notice how each step on this ladder adds one layer of complexity while keeping the foundational pattern intact. If you skip steps on this ladder, the harder problems will break your intuition.

Spotting DP and Writing the Recurrence in Words

You are looking at a dynamic programming problem when it meets two strict conditions. First, it has overlapping subproblems, meaning the same smaller problems appear repeatedly in the decision tree. Second, it has optimal substructure, meaning the global optimal solution can be constructed efficiently from the optimal solutions of its subproblems. If a problem asks for the minimum cost, maximum profit, total number of ways, or a boolean check for a valid partition, suspect DP immediately.

Before you write a single line of code, write the recurrence in plain English sentences on your scratchpad. For House Robber, write: "The max money I can steal up to house $i$ is either the money from house $i$ plus the best total from two houses ago, or just the best total from the previous house, whichever is larger."

If you cannot explain the transition between states in ordinary human language, code will only obscure your confusion. Writing the rule in words forces your brain to clarify the exact choice you are making at every single step.

Use DSA Tracker to practice these exact patterns in order without jumping straight to hard problems.

Trace the recursive tree for house robber on paper before writing your next solution.