Dynamic Programming for Beginners: Thinking in Subproblems

I remember the exact moment DP stopped scaring me. I was solving the coin change problem for maybe the fifth time, still not really understanding it, when my mentor at the time asked me one simple question: "Forget the code. If I gave you the answer for a smaller amount, could you use it to build the answer for a bigger amount?" That's it. That one question is the entire idea behind Dynamic  Programming. Everything else the tables, the recursion, the dp[i][j] arrays is just bookkeeping around that one question.

Most people struggle with DP not because it's mathematically hard, but because it's taught backwards. Courses show you a table full of numbers and tell you to fill it in following a formula, without ever explaining where that formula came from. You end up memorizing patterns instead of understanding them and the moment a new problem doesn't match a pattern you've seen before, you freeze.

This article is not going to give you 50 DP problems to memorize. It's going to slow down and show you exactly how to think when you see a new problem, so that when you sit in an interview and see a DP question you've genuinely never seen before, you can still work it out the same way you'd work out anything else, one honest step at a time.

What Dynamic Programming Actually Is

Here's the simplest way I can put it: Dynamic Programming is just recursion with a memory.

That's genuinely most of it. If you already know how to break a problem into smaller versions of itself which is exactly what recursion is then you already know 80% of Dynamic Programming. The remaining 20% is noticing that your recursion keeps solving the exact same smaller problem over and over again and deciding to save that answer the first time so you never have to solve it twice.

Think about it like this. Imagine you're asked "how many ways can you climb a staircase of 30 steps, taking either 1 or 2 steps at a time?" To answer this for 30 steps, you'd naturally think: "well, my last move was either a 1-step or a 2-step, so the answer for 30 steps is just the answer for 29 steps plus the answer for 28 steps." That's the whole insight. You didn't need to know the term "Dynamic Programming" to think that you just broke a big problem into smaller versions of the same problem. DP is simply the discipline of doing this properly and being smart about not repeating work.

A useful real-life comparison: imagine you're calculating your monthly expenses and you calculate your weekly totals along the way instead of adding up every single transaction from scratch every time someone asks you a new question like "what did I spend in the last two weeks?" You reuse the weekly totals you already calculated. Nobody taught you that in a computer science class you did it naturally because redoing the same addition over and over felt wasteful. DP is that same instinct, applied to code.

The Two Things Every DP Problem Needs

Not every problem can be solved with Dynamic Programming and knowing when it applies is half the battle. A problem is a good DP candidate when it has these two properties:

• Overlapping subproblems solving the big problem requires solving the same smaller problem multiple times. If every subproblem you encounter is completely different from every other one, there's nothing to save and reuse and DP won't help you.
• Optimal substructure the best answer to the big problem can be built directly from the best answers to its smaller pieces. If the best way to solve the whole problem has nothing to do with the best way to solve its smaller pieces, DP breaks down.

Here's a real example of a problem that does not have optimal substructure, just to make this concrete: finding the longest simple path between two points in a graph. You'd think you could build the longest path from smaller longest paths, but you can't because a path can't repeat a node and the "best" smaller path might use up a node that the bigger path also desperately needs. That single restriction breaks the substructure, which is exactly why this particular problem is much harder than typical DP problems and doesn't have a simple DP solution.

Don't worry about spotting these two properties perfectly right away. In practice, most beginners learn to recognize them by first attempting a plain recursive solution and then noticing the repeated work by eye which is exactly what the next section walks through.

Dynamic Programming Approaches: Recursion, Memoization and Tabulation

1. Recursion First, DP Second

Here's advice I give every single person I mentor through DP: never try to write a DP solution directly. Write the plain, honest recursive solution first, even if it's slow. DP is not a separate way of thinking it's an optimization you apply on top of a recursive solution you already understand.

Let's use the staircase problem from earlier: count the number of ways to climb n steps, taking 1 or 2 steps at a time.

The recursive thinking, in plain words: "the number of ways to reach step n equals the number of ways to reach step n-1, plus the number of ways to reach step n-2 because your very last move to reach step n was either a single step from n-1 or a double step from n-2."

public class ClimbingStairsBruteForce {
    public static int countWays(int n) {
        // base cases: 0 steps has exactly 1 way (do nothing),
        // 1 step has exactly 1 way
        if (n == 0 || n == 1) {
            return 1;
        }
        return countWays(n - 1) + countWays(n - 2);
    }
}

This is correct. Try it on paper for n = 4: ways to reach 4 = ways to reach 3 + ways to reach 2. If you keep expanding this out by hand, you'll get the right answer every time. But if you actually run this for n = 40, it will take a noticeably long time. That slowness is not a coincidence it's a big, visible clue that something is being repeated unnecessarily, which brings us to the next section.

Overlapping Subproblems Seeing the Repeated Work

Let's actually draw out what countWays(5) looks like when it expands. I want you to see this with your own eyes, not just take my word for it.

                        countWays(5)
                       /            \
              countWays(4)         countWays(3)
              /        \             /        \
      countWays(3)  countWays(2)  countWays(2)  countWays(1)
       /      \        /    \       /    \
countWays(2) countWays(1) ...   ...

Look closely at this tree. countWays(3) appears twice. countWays(2) appears three times. If this were countWays(40) instead of countWays(5), the smaller values like countWays(2) and countWays(3) would appear thousands, even millions of times, each one recalculated completely from scratch every single time, producing the exact same answer every time it's called.

This is the "overlapping subproblems" property from Section 2, made visible. And once you can see it this clearly, the fix becomes obvious: the very first time you calculate countWays(3), just remember the answer. Every future time you need countWays(3), look up the answer instead of recalculating it. That's it. That's Dynamic Programming.

2. Memoization: Remembering What You Already Solved

Memoization is the most natural first step from brute-force recursion, because you barely have to change your code you just add a "memory" to it.

import java.util.*;

public class ClimbingStairsMemoized {
    public static int countWays(int n) {
        Map<Integer, Integer> memo = new HashMap<>();
        return countWaysHelper(n, memo);
    }
    private static int countWaysHelper(int n, Map<Integer, Integer> memo) {
        if (n == 0 || n == 1) {
            return 1;
        }
        // if we've already solved this exact subproblem, reuse the answer
        if (memo.containsKey(n)) {
            return memo.get(n);
        }
        int result = countWaysHelper(n - 1, memo) + countWaysHelper(n - 2, memo);
        memo.put(n, result); // remember this answer before returning it
        return result;
    }
}

Compare this to the brute-force version the actual logic line, countWaysHelper(n - 1, memo) + countWaysHelper(n - 2, memo), is exactly the same. All we added was a check at the top ("have I solved this before?") and a save at the bottom ("remember this before I return"). This is why I always tell people memoization is the easiest possible entry point into DP you're not learning a new way to think, you're just adding a memory to a way of thinking you already had.

This one small change takes the time complexity from something that roughly doubles with every step you add, down to a straight line every value from 0 to n gets calculated exactly once.

3. Tabulation: Building the Answer From the Ground Up

Tabulation flips the direction. Instead of starting at the big problem and recursing down to small ones, you start at the smallest problems and build your way up to the big one usually using a simple loop and an array or table, with no recursion at all.

public class ClimbingStairsTabulation {
    public static int countWays(int n) {
        if (n == 0 || n == 1) {
            return 1;
        }
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
}

Here's a genuinely helpful way to think about the difference: memoization asks the question top-down "to solve n, what smaller things do I need?" and answers those smaller things as it goes. Tabulation answers bottom-up "let me solve 0, then 1, then 2, then 3..." and just keeps going until it naturally arrives at n, using answers it already built along the way.

One more thing worth noticing here: in this particular problem, at any point you only ever need the previous two values, dp[i-1] and dp[i-2] you don't actually need the whole array. So you could reduce this further to just two variables instead of a full array, cutting the space down from O(n) to O(1). I mention this now because "can I reduce the space" is a question worth asking after almost every DP solution you write, once it's already working correctly.

Memoization vs Tabulation When to Use Which

Beginners often ask me which one they should default to, so here's a genuinely practical comparison, not just a theoretical one.

My honest, practical advice: learn to write the recursive brute-force solution and the memoized version first, always. Once that's working and you deeply understand why it works, converting it to tabulation is a mechanical exercise you're just replacing recursive calls with a loop that fills the table in the right order. Trying to jump straight to tabulation before you understand the recursive shape of the problem is exactly why so many beginners find DP tables confusing they're looking at the "translated" version without ever seeing the "original" it was translated from.

A Simple Framework to Approach Any DP Problem

Here is the exact sequence I walk through, every single time, regardless of how unfamiliar the problem looks:

• Step 1 Define what a subproblem means, in plain English, before writing any code. For example: "dp[i] means the number of ways to climb the first i steps," or "dp[i] means the minimum number of coins needed to make amount i." If you can't say this sentence clearly, you're not ready to write code yet.
• Step 2 Figure out the base cases. What's the smallest version of this problem, small enough that you already know the answer without any calculation? Usually this is 0, an empty string, an empty array or amount 0.
• Step 3 Find the recurrence relation. Ask: "if I already had the answers to slightly smaller subproblems, how would I combine them to get the answer to this one?" This is almost always the hardest and most important step and it's worth spending real time here, on paper, before touching a keyboard.
• Step 4 Write the brute-force recursive solution first, using exactly the definition and recurrence from steps 1 to 3.
• Step 5 Identify the repeated subproblems, either by drawing the recursion tree like we did earlier or simply by noticing the function is called with the same arguments more than once.
• Step 6 Add memoization, then convert to tabulation once you're comfortable and finally consider whether the space can be reduced.

I want to be honest with you: Step 3 is where almost everyone gets stuck and it's normal. The recurrence relation is genuinely the creative, hard-thinking part of DP. Steps 4 through 6 are mostly mechanical once Step 3 is right. So when you're practicing, don't rush past Step 3 just to get to code faster sit with it, work through small examples by hand and let the pattern reveal itself the way it did with the staircase problem.

Dynamic Programming Examples

Example 1 ~ Climbing Stairs

We've already built this one piece by piece, so let's just consolidate it using the framework directly, since seeing the full framework applied cleanly, start to finish, is genuinely more useful than seeing five different scattered examples.

• Subproblem definition: dp[i] = number of distinct ways to reach step i, taking 1 or 2 steps at a time.
• Base cases: dp[0] = 1 (there's exactly one way to be at the ground don't move at all), dp[1] = 1 (only one way, a single 1-step).
• Recurrence: dp[i] = dp[i-1] + dp[i-2], because your last move to reach step i was either a 1-step from i-1 or a 2-step from i-2.
• Final code: the tabulated version from Section 6, which runs in O(n) time and can be reduced to O(1) space.

This problem, by the way, is secretly the Fibonacci sequence wearing a costume. Once you notice that, you'll start noticing it show up disguised in a surprising number of other problems too.

Example 2 ~ Coin Change

The problem: given a set of coin denominations and a target amount, find the minimum number of coins needed to make that exact amount. If it's not possible, return -1. Example: coins [1, 3, 4], amount 6 → answer is 2 (using 3 + 3).

• Subproblem definition: dp[amount] = the minimum number of coins needed to make exactly amount.
• Base case: dp[0] = 0 making amount 0 needs zero coins, obviously.
• Recurrence: for each amount, try using every available coin as the "last coin used." If I use a coin of value c as my last coin, then I need dp[amount - c] + 1 coins total the answer for the remaining amount, plus this one coin. Try every coin and take the smallest result: dp[amount] = min(dp[amount - c] + 1) for every coin c that's less than or equal to amount.

This recurrence is worth sitting with for a second, because it's a genuinely different flavor from the staircase problem instead of a fixed formula like dp[i-1] + dp[i-2], we're trying multiple options and picking the best one. This "try every option, take the best" shape is extremely common in DP, so it's worth recognizing on its own.

public class CoinChangeRecursive {

    public static int minCoins(int[] coins, int amount) {
        int ans = helper(coins, amount);
        return ans == Integer.MAX_VALUE ? -1 : ans;
    }
    private static int helper(int[] coins, int amount) {

        // Base case
        if (amount == 0)
            return 0;
        if (amount < 0)
            return Integer.MAX_VALUE;
        int min = Integer.MAX_VALUE;
        for (int coin : coins) {
            int result = helper(coins, amount - coin);
            if (result != Integer.MAX_VALUE) {
                min = Math.min(min, result + 1);
            }
        }
        return min;
    }
    public static void main(String[] args) {
        int[] coins = {1,3,4};
        System.out.println(minCoins(coins,6)); // 2
    }
}

Complexity

• Time: O(k^amount) (Exponential)
• Space: O(amount) recursion stack

where k = number of coin denominations.

Memoization (Top-Down DP)

import java.util.Arrays;

public class CoinChangeMemoization {

    public static int minCoins(int[] coins, int amount) {
        int[] memo = new int[amount + 1];
        Arrays.fill(memo, -2);   // -2 = not computed
        int ans = helper(coins, amount, memo);
        return ans == Integer.MAX_VALUE ? -1 : ans;
    }

    private static int helper(int[] coins, int amount, int[] memo) {
        if (amount == 0)
            return 0;
        if (amount < 0)
            return Integer.MAX_VALUE;
        if (memo[amount] != -2)
            return memo[amount];
        int min = Integer.MAX_VALUE;
        for (int coin : coins) {
            int result = helper(coins, amount - coin, memo);
            if (result != Integer.MAX_VALUE) {
                min = Math.min(min, result + 1);
            }
        }
        memo[amount] = min;
        return min;
    }
    public static void main(String[] args) {
        int[] coins = {1,3,4};
        System.out.println(minCoins(coins,6)); // 2
    }
}

Complexity

• Time: O(amount × numberOfCoins)
• Space: O(amount)

Tabulation (Bottom-Up DP)

import java.util.Arrays;

public class CoinChangeTabulation {

    public static int minCoins(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for (int currentAmount = 1; currentAmount <= amount;currentAmount++) {
            for (int coin : coins) {
                if (coin <= currentAmount && dp[currentAmount - coin] != Integer.MAX_VALUE) {
                    dp[currentAmount] = Math.min([currentAmount], dp[currentAmount - coin] + 1);
                }
            }
        }
        return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
    }
    public static void main(String[] args) {
        int[] coins = {1,3,4};
        System.out.println(minCoins(coins,6)); // 2
    }
}

Complexity

• Time: O(amount × numberOfCoins)
• Space: O(amount)

Tracing through coins = [1, 3, 4], amount = 6:

dp[0]=0. dp[1]: try coin 1 → dp[0]+1=1. dp[2]: try coin 1 → dp[1]+1=2. dp[3]: try coin 1 → dp[2]+1=3, try coin 3 → dp[0]+1=1 (better!) → dp[3]=1. dp[4]: try coin 1 → dp[3]+1=2, try coin 4 → dp[0]+1=1 (better!) → dp[4]=1. dp[5]: try coin 1 → dp[4]+1=2, try coin 3 → dp[2]+1=3, try coin 4 → dp[1]+1=2 → dp[5]=2. dp[6]: try coin 1 → dp[5]+1=3, try coin 3 → dp[3]+1=2 (best) → dp[6]=2.

Final answer: dp[6] = 2, which matches using two 3-coins. The Integer.MAX_VALUE check before adding 1 exists specifically to avoid a subtle bug if you tried to compute dp[currentAmount - coin] + 1 when that value is still "impossible" (represented by MAX_VALUE), you'd cause an integer overflow, silently producing a wrong, very negative-looking number instead of correctly recognizing it's still unreachable.

Example 3 ~ Longest Common Subsequence

The problem: given two strings, find the length of their longest common subsequence, a sequence of characters that appears in both strings in the same relative order, but not necessarily next to each other. Example: "abcde" and "ace" → the longest common subsequence is "ace", length 3.

This is the first example in this article with two changing inputs instead of one, which means our subproblem needs two dimensions instead of one this is a very natural next step once single-dimension DP feels comfortable.

• Subproblem definition: dp[i][j] = the length of the longest common subsequence between the first i characters of string A and the first j characters of string B.
• Base case: dp[0][j] = 0 and dp[i][0] = 0 for any i or j if either string is empty, there's obviously no common subsequence at all.
• Recurrence: compare the current characters, A[i-1] and B[j-1] (using i-1 and j-1 because of the 0-indexing offset). If they match, this character extends whatever the best subsequence was without either of these two characters: dp[i][j] = dp[i-1][j-1] + 1. If they don't match, this character can't help you, so take the better of two options skip the current character of A or skip the current character of B: dp[i][j] = max(dp[i-1][j], dp[i][j-1]).

public class LongestCommonSubsequence {
    public static int lcsLength(String a, String b) {
        int m = a.length();
        int n = b.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (a.charAt(i - 1) == b.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[m][n];
    }
}

For "abcde" and "ace", this correctly builds up to dp[5][3] = 3. I'd genuinely encourage you to draw this 6x4 grid by hand and fill it in yourself it takes about five minutes and seeing the table fill in with your own hand, cell by cell, does more for your understanding than reading about it ever will.

Example 4 ~ 0/1 Knapsack

The problem: you have a bag that can carry a maximum weight W. You have a set of items, each with its own weight and value. For each item, you can either take it completely or leave it completely no partial items. Maximize the total value you can carry without exceeding the weight limit.

• Subproblem definition: dp[i][w] = the maximum value achievable using only the first i items, with a bag capacity of w.
• Base case: dp[0][w] = 0 for any capacity with zero items available, you can carry zero value, no matter how big the bag is.
• Recurrence: for each item, you have exactly two choices skip it or take it (only if it fits). Skipping it means dp[i][w] = dp[i-1][w]. Taking it means dp[i][w] = dp[i-1][w - weight[i]] + value[i], but only if weight[i] <= w. Take whichever choice gives the bigger value.

public class Knapsack {
    public static int maxValue(int[] weights, int[] values, int capacity) {
        int n = weights.length;
        int[][] dp = new int[n + 1][capacity + 1];
        for (int i = 1; i <= n; i++) {
            for (int w = 0; w <= capacity; w++) {
                // option 1: skip this item
                dp[i][w] = dp[i - 1][w];
                // option 2: take this item, if it fits
                if (weights[i - 1] <= w) {
                    int valueIfTaken = dp[i - 1][w - weights[i - 1]] + values[i - 1];
                    dp[i][w] = Math.max(dp[i][w], valueIfTaken);
                }
            }
        }
        return dp[n][capacity];
    }
}

Notice something worth calling out explicitly: this problem's recurrence has the exact same shape as coin change and the exact same shape as longest common subsequence at every step, you're comparing a small number of concrete choices and picking the best one. Once you've solved five or six DP problems using this framework honestly, you start to notice this "compare your options, pick the best" shape everywhere and that recognition, not memorization, is what real DP skill actually looks like.

How to Spot a DP Problem in an Interview

You won't always get a problem that says "use Dynamic Programming" in the title. Here are the honest, practical signals I look for, the same ones I'd want a candidate to notice:

• The question asks for a maximum, minimum or count of ways "what's the minimum number of coins," "how many distinct ways," "what's the longest possible sequence."
• You can describe the answer to a bigger case using the answer to smaller cases of the exact same problem this is the recurrence relation forming in your head, even before you've written anything down.
• Your first working idea is a recursive brute-force solution and it's clearly slow because of repeated, identical subproblems this is your cue to look for a DP transformation, exactly as we did with the staircase problem.
• The problem involves making a sequence of decisions, where each decision affects what options remain later like choosing which items to include, which coins to use or which characters to match.

If none of these signals show up, don't force DP onto the problem just because it feels like the "advanced" thing to reach for. I've seen candidates try to jam a DP solution onto a problem that just needed a simple loop or a two-pointer approach and the forced complexity usually creates more bugs than it solves.

Common Mistakes Beginners Make

• Jumping straight to the DP table without writing the recursive version first. This is the single biggest reason DP feels confusing you're staring at a formula with no memory of where it came from.
• Not clearly stating what dp[i] (or dp[i][j]) actually means in plain words. If you can't say the definition out loud in one clean sentence, the code that follows is built on a shaky foundation and bugs become very hard to track down.
• Getting the base cases wrong, especially off-by-one issues around index 0 this is genuinely the most common source of small, annoying bugs in DP code.
• Confusing "the answer to a smaller version of the exact same problem" with "just a smaller number." The recurrence has to actually represent the same question, just on less data not a vaguely related smaller calculation.
• Trying to optimize space before the logic is even correct. Get a working recursive or tabulated solution first. Reducing a 2D array to a few variables is a nice final touch, not a starting point.
• Giving up after one confusing problem and deciding "I'm just not a DP person." I've mentored plenty of engineers who felt exactly this way and every single one of them got noticeably better after deliberately working through eight to ten problems using the same framework from Section 8, every time, without skipping steps.

How to Practice DP Without Burning Out

• Solve the same problem shape more than once, a few days apart, without looking at your old solution. Repetition on a small, well-chosen set of problems builds real pattern recognition far better than rushing through fifty different problems once each.
• Always write the plain recursive version first, even after you've gotten comfortable with DP this habit alone prevents most of the confusion beginners run into later on harder problems.
• Draw the recursion tree by hand for at least your first ten DP problems, the way we did for the staircase problem. It feels slow at first, but it's exactly what builds the intuition to skip this step later.
• Group problems by their recurrence shape, not by their surface topic climbing stairs and house robber are secretly similar; coin change and knapsack are secretly similar. Noticing these families matters more than the total number of problems you've attempted.
• Give yourself real time on Step 3 from the framework the recurrence relation before looking at a hint or a solution. The struggle in that step is where the actual learning happens; skipping straight to the answer skips the part that builds skill.

Frequently Asked Questions (FAQ)

1. Do I need to be good at math to understand Dynamic Programming?

No. DP is much more about breaking a problem into smaller, honest pieces than it is about advanced math. If you can explain a smaller version of a problem in plain English, you already have the core skill.

2. Should I learn recursion before learning DP?

Yes, genuinely. DP builds directly on top of recursion, and trying to learn DP without being comfortable with recursion first is exactly why so many beginners find it confusing.

3. What's the difference between DP and plain recursion?

Plain recursion may solve the same subproblem many times over. DP notices this repeated work and saves the answer the first time, either through memoization or tabulation, so it's never recalculated.

4. How do I know if a problem needs a 1D or 2D DP array?

It usually matches the number of things that are "changing" in the problem. One changing input (like an amount or a position in a single array) usually means 1D. Two changing inputs (like two strings or an item index plus a weight limit) usually means 2D.

5. Is memoization or tabulation better for interviews?

Either is generally acceptable, but memoization is often easier to arrive at naturally, since it grows directly out of the recursive solution you'd write anyway. Mention both if you have time.

6. Why does my memoized solution still feel slow?

Check that you're actually using the memo correctly. A common bug is checking or saving the memo with the wrong key or checking it after doing the expensive work instead of before.

7. What if I can't find the recurrence relation at all?

Go back to a small, concrete example and solve it entirely by hand, writing down every decision you make along the way. The pattern in your own manual decisions is usually the recurrence relation, just not yet written as a formula.

8. Are DP problems always about finding a maximum or minimum?

Not always, but very often counting the number of ways to do something is also extremely common, as we saw with the staircase problem.

9. Do I need to know Dynamic Programming for every coding interview?

Not every interview will include a DP question, but it shows up often enough at mid to senior levels that it's worth being genuinely comfortable with, not just superficially aware of.

10. How many DP problems should I solve before I feel confident?

There's no universal number, but most people I've mentored start feeling real, honest confidence somewhere between 25 and 40 problems, provided they're following the framework each time rather than jumping straight to memorized solutions.

11. Is Dynamic Programming the same as Greedy algorithms?

No. Greedy algorithms make one locally best choice at each step and never look back. DP considers multiple possible choices and combines the best results from smaller subproblems, which handles cases where the locally best choice isn't actually the globally best one.

12. Can every recursive solution be turned into a DP solution?

Only if the problem has overlapping subproblems, as described in Section 2. If every recursive call is solving something genuinely different, there's nothing to save and reuse, and DP won't offer any benefit.

13. Why do some DP solutions use a 2D array when the problem only mentions one array?

Sometimes an extra dimension is needed to represent an additional piece of changing information, like "how much capacity is left" in the knapsack problem, even though there's only one array of items.

Key Takeaways

• Dynamic Programming is recursion with a memory nothing more mysterious than that.
• Always write the honest, brute-force recursive solution first and only then look for repeated subproblems to optimize.
• A DP problem needs two things to actually work: overlapping subproblems and optimal substructure.
• The real skill in DP is finding the recurrence relation everything after that is largely mechanical.
• Memoization and tabulation solve the same problem from two different directions, top-down and bottom-up and it's worth being comfortable with both.
• Learn a small set of problems deeply, by their recurrence shape, rather than rushing through a large number of problems shallowly.

Related Articles

How to Approach Any DSA Interview Problem: A Complete Step-by-Step Guide

Sliding Window Pattern: When and How to Use It

What is Two Pointer Approach : When and How to use It

Backtracking for Beginners: The Complete Guide from Basics to Advanced Patterns

Real Interview Experiences: Google, Amazon and Meta

The Ultimate DSA Practice Sheet for FAANG Interviews