Recognizing DP Problems

1. The Two Pillars of Dynamic Programming

A problem can be solved efficiently using dynamic programming if and only if it exhibits two key properties. Let's define them formally.

Let's break down what you just saw.

a) Optimal Substructure

A problem has optimal substructure if an optimal solution to the overall problem can be constructed from the optimal solutions of its subproblems.

The shortest path example from the video is a perfect illustration:

• Problem: Find the shortest path from San Francisco to San Diego.
• Subproblems: Find the shortest path from SF to Los Angeles, and the shortest path from LA to San Diego.
• Optimal Substructure: If you combine the shortest path from SF to LA with the shortest path from LA to SD, you are guaranteed to have the shortest path from SF to SD overall. The optimal solution to the big problem is built from the optimal solutions of the smaller ones.

A great heuristic for spotting this property is to ask yourself: "Can I solve this problem recursively?" If you can define the solution for a problem of size n in terms of solutions for problems of a smaller size (e.g., n-1, n-2), it likely has optimal substructure.

b) Overlapping Subproblems

A problem has overlapping subproblems if a recursive algorithm solves the same subproblems over and over again, rather than generating new subproblems at each step.

As you saw in the last lesson and again in the video, the recursive solution for Fibonacci numbers is the classic example. Calculating fib(5) requires calculating fib(4) and fib(3). But the fib(4) calculation also requires calculating fib(3), leading to redundant computations. The recursion tree clearly shows these "overlapping" calls.

It is the presence of both of these properties that makes a problem a candidate for dynamic programming.

2. How to Recognize a DP Problem in an Interview

Now for the practical part: you're in an interview, you get a problem, and the clock is ticking. How do you quickly and confidently determine if it's a DP problem?

There are several strong signals to look for.

Let's consolidate these ideas into a three-step process.

Step 1: Look for Keywords and Problem Types

Many DP problems fall into two categories. Being able to spot the category is a strong first signal.

To summarize, be on the lookout for problems that ask you to:

1. Find an optimal value: Look for keywords like "maximum," "minimum," "longest," "shortest," "best," etc.
   • Example: What is the longest common subsequence? What is the minimum number of coins to make change?
2. Count the number of ways: Look for keywords like "how many ways," "total number of possibilities," "count all," etc.
   • Example: How many ways are there to climb n stairs? Count the number of unique paths in a grid.

If your problem fits one of these descriptions, move to the next step.

Step 2: Formulate a Brute-Force Recursive Solution

Try to define the problem in terms of itself. This is your test for optimal substructure.

• For the "Climbing Stairs" problem: ways(n) = ways(n-1) + ways(n-2). The solution for n steps depends on the solutions for n-1 and n-2 steps.
• For the "Longest Common Subsequence" of strings A and B: The solution depends on what you do with the last characters of A and B, leading to subproblems with shorter strings.

If you can write down a recurrence relation, you've confirmed optimal substructure.

Step 3: Draw the Recursion Tree to Find Overlaps

This is the definitive test for overlapping subproblems. Take your recursive relation from Step 2 and draw the tree of function calls for a small example.

As the article by Tarun Jain notes, this is a critical step:

"If we have an optimization or counting problem, then one of the simple ideas would be to design a recursive solution, draw the recursion tree for some sample input and identify the repeated sub-problems scenario. If subproblems are repeated then the given problem can be solved using dynamic programming."

If you see the same function call (e.g., fib(3)) appearing in multiple branches of the tree, you have confirmed overlapping subproblems. At this point, you can confidently state to your interviewer: "This problem has optimal substructure and overlapping subproblems, which suggests that a dynamic programming approach would be effective."

3. Common DP Patterns

As you practice, you'll start recognizing entire categories of problems. Being familiar with these patterns is the high-ROI strategy you're looking for, as many interview questions are variations of these classics.

The following video from NeetCode introduces five common DP patterns. For this lesson, we won't focus on the full solution, but on how each problem is broken down into subproblems.

Let's briefly summarize the subproblem structure for these patterns:

• 0/1 Knapsack: Given an item, the decision is to either include it or skip it.
  • If you include item i with weight w and value v, the subproblem becomes finding the optimal value for the remaining capacity and remaining items.
  • If you skip item i, the subproblem is finding the optimal value for the same capacity but with the remaining items.
• Longest Common Subsequence (LCS): Given two strings, the decision is based on comparing their last characters.
  • If the characters match, they contribute to the LCS. The subproblem is finding the LCS of the strings without those last characters.
  • If they don't match, you have two choices: find the LCS by either removing the last character from the first string, or removing it from the second string. The solution is the better of these two subproblems.

Recognizing these fundamental decision-making processes is key to identifying the underlying DP pattern.

Conclusion

Mastering dynamic programming begins with pattern recognition. Today, you learned the theoretical foundation and the practical heuristics for identifying problems where DP is a suitable and efficient strategy.

Key Takeaways:

• A problem is a candidate for dynamic programming if it has both optimal substructure and overlapping subproblems.
• Optimal Substructure means the optimal solution can be built from optimal solutions to smaller subproblems. You can test for this by trying to formulate a recursive solution.
• Overlapping Subproblems means a naive recursive solution would re-compute the same subproblems multiple times. You can test for this by drawing the recursion tree and looking for duplicate nodes.
• In an interview, look for optimization (min/max/longest) or counting ("how many ways") problems as your first clue.
• Common DP patterns like Knapsack and Longest Common Subsequence revolve around making a sequence of decisions that break the problem down into smaller instances.

You now have the diagnostic tools to identify DP problems. In our next lesson, we will build upon this by learning how to convert the recursive, memoized solution you're familiar with into an iterative, bottom-up DP solution, a technique also known as tabulation. This will complete your foundational understanding of the two main DP approaches.