Introduction
Hello! Welcome to our new module on Dynamic Programming (DP). In the last module, we explored graph traversal algorithms, culminating in a method for counting connected components. As we wrapped up, I mentioned that we'd be shifting to a powerful technique for optimizing slow recursive algorithms. That technique is dynamic programming.
You've already worked with recursion, like in our lessons on Merge Sort or Depth-First Search. You may have noticed that some recursive solutions can be very inefficient, especially when they repeatedly solve the same smaller problems. Dynamic Programming is a powerful algorithmic paradigm designed to tackle precisely this issue. It's one of the most important topics for technical interviews, as it demonstrates your ability to break down complex problems and write efficient code.
In this first lesson on DP, our goal is to build a solid foundation. We won't be writing complex DP code just yet. Instead, we'll focus on learning how to identify problems where DP is the right tool for the job. Specifically, you will learn to spot two key characteristics: optimal substructure and overlapping subproblems.
What is Dynamic Programming?
At its core, Dynamic Programming is an optimization technique. It transforms problems that would otherwise have an exponential time complexity (like many brute-force recursive solutions) into much more efficient polynomial-time solutions.
The central idea is simple: solve each smaller subproblem only once and store its result. When you encounter the same subproblem again, you simply look up the stored answer instead of re-computing it.
Dynamic Programming (DP) Introduction
To get a formal definition, let's start with this introductory article from GeeksforGeeks. It clearly explains the 'why' behind DP.
Read the first two sections, up to (but not including) 'When to Use Dynamic Programming (DP)?'. Focus on the core idea of storing results to avoid recomputation.
The name "Dynamic Programming" can be a little misleading. It was coined by mathematician Richard Bellman in the 1950s. Here, "programming" doesn't refer to coding but to planning or decision-making, and "dynamic" refers to the time-varying nature of the problems.
The Two Hallmarks of a DP Problem
For a problem to be a good candidate for a dynamic programming solution, it must exhibit two specific properties. Think of these as the two essential ingredients.
Let's dive into what each of these properties means. The following video provides excellent, intuitive explanations for both.
A Beginner's Guide to Dynamic Programming
Watch the first part of 'A Beginner's Guide to Dynamic Programming' by Matt Guest. It will introduce both core concepts with clear, visual examples.
Watch from 01:39 to 04:36. The video first explains 'optimal substructure' using a shortest-path example, and then 'overlapping subproblems' using the Fibonacci sequence. Pay close attention to the recursion tree diagram for Fibonacci—it perfectly illustrates the problem of repeated work.
Let's break those two concepts down further.
1. Optimal Substructure
A problem has optimal substructure if its overall optimal solution can be constructed from the optimal solutions of its subproblems.
The shortest path example from the video is classic: if the shortest path from San Francisco to San Diego goes through Los Angeles, then the path taken from SF to LA must be the shortest path between those two cities. You can't have a globally optimal path that uses a sub-optimal sub-path.
An Important Counterexample: The Longest Path Problem
It's equally important to know when a problem lacks optimal substructure. Consider finding the longest simple path (a path with no repeated nodes) in a graph. The longest path between two nodes is not necessarily made up of the longest paths of its sub-segments, because combining them might create a cycle, which isn't allowed.
Dynamic Programming | Set 2 (Optimal Substructure Property) | GeeksforGeeks
This short clip from GeeksforGeeks clearly explains why the Longest Path problem does not have optimal substructure, providing a crucial counterpoint to the Shortest Path example.
Watch from 01:13 to 02:12 to understand this counterexample.
2. Overlapping Subproblems
A problem has overlapping subproblems if a recursive algorithm solves the same subproblems multiple times.
The Fibonacci sequence you saw in the first video is the quintessential example. To calculate fib(5), you need fib(4) and fib(3). But to calculate fib(4), you also need fib(3). The fib(3) subproblem is solved twice. As the numbers get larger, the amount of redundant calculation grows exponentially. DP saves the day by calculating fib(3) once, storing the result, and reusing it.
If a problem can be broken down into subproblems, but the subproblems don't overlap (like in Merge Sort, where each half of the array is sorted independently), then a simple "divide and conquer" approach is sufficient, and DP isn't necessary.
Identifying DP Properties in an Interview Problem
Let's apply these concepts to a typical interview-style problem. This will help you move from abstract definitions to practical application.
Problem: The House Robber
You are a treasure hunter planning to rob houses along a street. Each house has a certain amount of treasure. The only constraint is that you cannot rob two adjacent houses, as it will trigger an alarm. Given a list of non-negative integers representing the treasure in each house, what is the maximum amount of treasure you can steal?
Example:
treasure = [3, 10, 4, 1, 5]If you rob house 1 (value 10), you can't rob house 0 or 2. An optimal solution would be to rob houses 0, 2, and 4 for a total of
3 + 4 + 5 = 12.
How can we determine if this has optimal substructure and overlapping subproblems?
Solving a Question with Dynamic Programming
This article from Hello Interview walks through this exact thought process for the 'House Robber' problem. It's a great example of how to analyze a problem from first principles.
Read the sections 'Why Dynamic Programming?', 'Optimal Substructure', and 'Overlapping Subproblems'. Pay attention to the logic: to decide on house i, you only need to know the best possible outcomes from the houses before it. This is the key insight for identifying optimal substructure.
As the article explains:
- Optimal Substructure: The maximum treasure you can get up to house
idepends on the maximum you could get up to housei-1(if you skip housei) and the maximum you could get up to housei-2(if you rob housei). The overall optimal solution is built from previous optimal solutions. - Overlapping Subproblems: To calculate the max treasure for house 5, you'll need the results for houses 3 and 4. To calculate it for house 6, you'll need results for houses 4 and 5. The result for house 4 is needed in both calculations—a clear sign of overlapping subproblems.
Quick Patterns for Spotting DP Problems
Beyond the two formal properties, there are several common problem patterns that often suggest a DP solution. Recognizing these can give you a valuable head start during an interview.
A Beginner's Guide to Dynamic Programming
Let's return to the 'Beginner's Guide' video. The final section provides a fantastic list of practical patterns to look out for.
Watch from 04:36 to 06:51. The video outlines five common indicators of a DP problem. Try to connect each pattern to problems you've seen before.
To summarize the patterns from the video:
- Sequential Decision-Making: Problems where you make a sequence of choices, and each choice affects future options (e.g., House Robber).
- Greedy Choice Property: Problems that seem like they could be solved greedily, but where the locally optimal choice isn't always globally optimal. DP explores all choices.
- State Transitions: Problems where you move from one "state" to the next based on a set of rules (e.g., Climbing Stairs, which we'll see soon).
- Path/Array Problems: Finding an optimal path in a grid or an optimal subsequence in an array (e.g., Longest Increasing Subsequence).
- Counting / Maximization / Minimization: Problems that ask "How many ways...?", "What is the maximum...?", or "What is the minimum...?".
Conclusion
In this lesson, we established the fundamental theory behind Dynamic Programming. You've learned how to identify problems that are suitable for a DP approach by looking for its two essential characteristics.
Key Takeaways:
- Dynamic Programming is an optimization technique that speeds up recursive algorithms by storing the results of subproblems to avoid recomputation.
- A problem is a candidate for DP if and only if it has both:
- Optimal Substructure: The optimal solution to the overall problem can be built from the optimal solutions to its smaller subproblems.
- Overlapping Subproblems: The same subproblems are encountered and solved multiple times in a brute-force recursive approach.
- Recognizing common patterns, such as maximization/minimization problems or those involving sequential decisions, can serve as a strong hint that DP might be the right approach.
Preview of the Next Lesson:
Now that you know how to identify a DP problem, the next step is to learn how to solve it. In our next lesson, we will take a classic DP problem, "Climbing Stairs," and walk through the first crucial step in any DP solution: formulating a brute-force recursive solution. This will form the foundation that we will then optimize using DP techniques in subsequent lessons.