Dynamic Programming Isn't Hard. You've Just Been Introduced to It Wrong.

Most people meet Dynamic Programming through a problem that looks like this: a 2D array, a nested loop, indices everywhere, and code that somehow produces a correct answer with no obvious explanation of why. They memorize the pattern, pass the interview, and still have no idea what DP actually is. That's the wrong way in. DP is not a coding pattern. It's a thinking pattern. And once you see what it's actually doing, the arrays and indices stop looking like magic and start looking like a natural consequence of a simple idea. This is Chapter 1 of a series that builds DP from scratch. No tables yet. No 2D arrays. Just the mindset, the mental model, and the exact thinking process you'll use for every DP problem that follows. The One Idea Behind All of DP Dynamic Programming has one core insight: If you've already solved a smaller version of a problem, don't solve it again. Store the answer and reuse it. That's it. Everything else, the tables, the recursion, the memoization, is just machinery built around that idea. How to Recognise a DP Problem This is the question that matters most when you're starting out. Before worrying about tables or recursion, you need to know: is this even a DP problem? Look for three things. Choices. At some point in the problem, you face a decision. Take the item or skip it. Go left or go right. Cut here or cut somewhere else. The exact choices vary by problem, but there's always a fork. Overlapping subproblems. When you draw out the recursion tree, the same smaller problem appears more than once. This is the signal that matters. Optimal substructure. The best answer to the big problem is built from the best answers to its smaller pieces. When you see a problem, ask yourself these questions in order: Are there choices at each step? ↓ Can the problem be broken into smaller versions of itself? ↓ Do the same smaller versions appear more than once? ↓ Is the answer based on finding the best / count / possibility? If the answer to these is yes, you're in DP territory. The Learning Path We'll Follow A lot of DP tutorials start with the table. That's like learning to drive by studying the engine. We're going the other way. Every DP problem in this series will follow the same order: We never jump to the table. We always start with the recursive thinking, identify where the wasted work is, and then apply DP to eliminate it. Two Components That Drive Every Recursive Solution Before you can convert recursion to DP, you need to write good recursion. Every recursive solution is built from exactly two things. The Base Case The base case answers one question: when do I stop? More precisely: what is the smallest valid input for this problem, and what is its answer? if n == 0: return 0 Here, n == 0 is the smallest problem we've decided to handle directly, and 0 is its answer. Before writing a single line of recursive logic, always ask: what is the smallest version of this problem, and what does it return? The Choice Diagram After the base case, ask: at the current step, what options do I have? Take the classic 0/1 Knapsack problem. You're at item i with remaining capacity W . You have exactly two choices: If wt[i] W: Only option - SKIP: Knapsack(i-1, W) The recursion is simply exploring these choices and returning the best result. Once you draw the choice diagram for any problem, the recursive code almost writes itself. From Recursion to DP: Two Roads Once you have a recursive solution, and you've confirmed the same subproblems are being solved repeatedly, you have two ways to fix it. Top-Down (Memoization) keeps the recursive structure intact but adds a cache. Before computing a state, check if it's already been solved. If yes, return the stored answer. If no, compute it, store it, and return it. # Conceptual memoization pattern if dp[state] is not None: return dp[state] # compute the answer dp[state] = result return dp[state] Bottom-Up (Tabulation) flips the direction entirely. Instead of starting from the big problem and recursing down, you start from the smallest problems and build upward, filling a table until you reach the answer you need. T[0][...] → T[1][...] → T[2][...] → ... → T[n][W] Both approaches produce the same answer. Which one to use depends on the problem. We'll see both in action across the problems that follow in this series. The Mental Model That Replaces Memorisation Don't memorise: "DP means a 2D array." Don't memorise: "Two recursive calls means DP." Instead, carry this one flowchart in your head: The table is just how you store answers. The real work is in recognising the repeated subproblems and drawing the choice diagram clearly before you write a single line of code. What's Coming in This Series This chapter covered the mindset. Everything that follows builds on it. The series will move through problems in a deliberate order, starting simple and adding complexity layer by layer: Recursion and Base Cases ↓ Memoization ↓ Tabulation ↓ 0/1 Knapsack Pattern ↓ Subset Sum, Equal Partition, Count Subsets ↓ Unbounded Knapsack - Rod Cutting, Coin Change ↓ LCS, LIS, Kadane's Algorithm ↓ Interval DP, DP on Trees Each problem in the series will follow the same nine-step order: understand the problem, identify choices, draw the choice diagram, find the base case, write recursion, find repeated states, add memoization, convert to tabulation, optimise if possible. We never skip to step eight. That's the whole point. What You Now Understand DP is not about arrays or patterns you memorise before an interview. It's about recognising that you've seen a subproblem before and refusing to solve it twice. The choices tell you the recursive structure. The base case tells you when to stop. The repeated states tell you where DP saves work. Everything else follows from those three things. Chapter 2 starts with recursion problems that build the muscle for spotting choices and base cases before we introduce any DP optimisation at all. If recursion still feels shaky, that's exactly the right place to start. Top comments (0)