Welcome to your first lesson on dynamic programming. This course is designed to build a strong, first-principles understanding of DP, moving from core concepts to the practical synthesis of solutions. Our goal today is to establish the fundamental conditions that make a problem suitable for a dynamic programming approach. By the end of this lesson, you will be able to characterize problems solvable by DP by identifying two key properties: optimal substructure and overlapping subproblems.
This foundational understanding is the "why" behind DP. It explains what structural properties in a problem signal that DP might be the right tool, distinguishing it from other recursive approaches like simple divide-and-conquer.
The Two Hallmarks of a DP Problem
Dynamic programming is fundamentally an optimization technique for a specific class of recursive problems. A naive recursive solution to these problems is often correct but inefficient, typically running in exponential time. DP provides a systematic way to optimize this to polynomial time. This optimization is possible only when the problem exhibits two specific properties.
Let's examine them one by one.
1. Overlapping Subproblems
Consider the naive recursive computation of Fibonacci numbers: . If we trace the execution for , we see that we compute twice, three times, and so on. The same subproblems are solved again and again. This property is called overlapping subproblems.
A graphical introduction to dynamic programming
This article provides an excellent visual demonstration of overlapping subproblems using the Fibonacci sequence. It contrasts the naive recursive call tree with a memoized version, which avoids recomputing results.
Please read the introduction and the first two sections, Fibonacci numbers and Using memoization. Pay close attention to the call tree diagrams showing the redundant computations. The article then introduces the core idea of memoization (caching) to solve this inefficiency. Finally, read the section on the bottom-up approach and observe the diagram that collapses the call tree into a subproblem dependency graph.
The key insight is that the number of unique subproblems is small (for Fibonacci, it's just subproblems, ), while the number of calls in the naive recursion is exponential. Dynamic programming, through a technique called memoization (a form of caching), stores the solution to each subproblem after computing it once. Subsequent calls that need the solution to that same subproblem simply look it up, eliminating the redundant work.
As the MIT OpenCourseWare lecture on dynamic programming explains, this simple idea is what turns an exponential-time algorithm into a polynomial-time one.
15. Dynamic Programming, Part 1: SRTBOT, Fib, DAGs, Bowling
This segment of the lecture uses the Fibonacci example to perfectly illustrate the cost of overlapping subproblems and the power of memoization.
Watch the segment from the introduction of Fibonacci to the explanation of the recursion tree. Notice how the lecturer identifies identical subproblems being computed multiple times. Then, continue watching from this discussion of how memoization—remembering and reusing solutions—collapses this redundant work. The analysis at the end connecting runtime to the number of subproblems is crucial: Time ≈ (# subproblems) * (work per subproblem).
In contrast, an algorithm like Mergesort also breaks a problem into subproblems. However, when sorting an array, the two halves it recursively sorts are disjoint. No subproblem is ever solved more than once. This is characteristic of divide-and-conquer algorithms, which are efficient without memoization because their subproblems do not overlap.
2. Optimal Substructure
The second property, optimal substructure, means that the optimal solution to the overall problem can be constructed from the optimal solutions to its subproblems.
This might sound tautological, but it's a specific structural property that not all problems possess. The classic example of optimal substructure is the shortest path problem. If the shortest path from node A to node C passes through node B, then the A-to-B portion of that path must be the shortest path from A to B. If it weren't, you could substitute the true shortest A-to-B path and get an even shorter A-to-C path, which is a contradiction.
A problem that lacks optimal substructure is finding the longest simple path (no repeated vertices) in an unweighted cyclic graph. Suppose the longest simple path from A to C goes through B. The subpath from A to B is not necessarily the longest simple path from A to B, because the globally optimal path might use nodes that a locally optimal path would need to "save" for the B-to-C segment.
For DP problems, optimal substructure is typically expressed via a recurrence relation. This relation defines how to compute the solution for a given problem from the solutions of its subproblems.
For example, in the "House Robber" problem, where you cannot rob adjacent houses, we can define f(i) as the maximum value obtainable from houses 0 to i. The recurrence relation is:
This expresses the two choices at house i:
- Rob house
i: Gain its value , but then you can only add the optimal solution from houses up toi-2. - Skip house
i: Gain nothing now, but you are free to take the optimal solution from houses up toi-1.
The optimal solution f(i) is constructed by taking the maximum of two options, each of which relies on the pre-computed optimal solutions to smaller subproblems (f(i-1) and f(i-2)).
Solving DP problems by SRTBOT Framework - MartinLwx's Blog
This article gives concise, direct definitions for our two key concepts.
Read the section What's the DP problem?. This reinforces the definitions of both properties and the distinction from divide-and-conquer.
Synthesis: The Subproblem Dependency Graph
The most powerful mental model for dynamic programming, especially given your background, is to view the problem as a Directed Acyclic Graph (DAG) of subproblem dependencies.
- Vertices are the unique subproblems.
- Directed Edges represent dependencies. An edge from subproblem
utov(u->v) means that the solution tovdepends on the solution tou.
The two properties map perfectly to this model:
- Overlapping Subproblems: A vertex in the DAG with an in-degree greater than one represents an overlapping subproblem. It's a dependency for multiple other subproblems.
- Optimal Substructure: The edges themselves, which are defined by the recurrence relation, represent the principle of optimal substructure. They show how larger problems are constructed from smaller ones.
The graph must be acyclic; otherwise, a subproblem would depend on itself, leading to an infinite recursion.
The process of solving a DP problem "bottom-up" is equivalent to processing the nodes of this DAG in a topological order. You start with the base cases (nodes with an in-degree of 0) and compute the values for subsequent nodes, ensuring that by the time you evaluate any node v, all its dependencies (nodes u for which an edge u -> v exists) have already been computed. This is directly analogous to how a compiler might evaluate dependencies in an expression tree or an instruction scheduler might order operations.
The following video provides a fantastic walkthrough of this DAG-centric view for two problems: Longest Increasing Subsequence and Box Stacking.
5 Simple Steps for Solving Dynamic Programming Problems
This video excels at visualizing DP problems as graphs. It makes the abstract concepts of subproblems and dependencies concrete.
First, watch the section on the Longest Increasing Subsequence (LIS), from the problem definition to the explanation of the DAG. See how an increasing subsequence is mapped to a path in the graph. The key idea is that the problem itself can be reframed as a longest-path problem on a DAG. Next, skip to the Box Stacking problem. Watch how it's also visualized as a DAG, starting at the visualization section. Here, a valid stack of boxes is a path in the graph. The subproblem is defined as the tallest stack with a specific box at the base, which corresponds to finding the longest path starting from a particular node.
This framing of DP as finding optimal paths on an implicit DAG is a recurring and powerful pattern. We even saw that the standard algorithm for single-source shortest paths on a DAG is itself a dynamic program. The recurrence is simply the relaxation step, performed in topological order.
Summary
To determine if a problem is a candidate for dynamic programming, you must verify it has both:
- Overlapping Subproblems: A recursive solution solves the same subproblems multiple times. This signals an opportunity for optimization via memoization.
- Optimal Substructure: The optimal solution to the overall problem can be constructed from the optimal solutions of its subproblems. This allows you to define a recurrence relation.
Together, these properties imply that the problem can be modeled as finding an optimal value over a subproblem dependency DAG. The DP algorithm is then simply a traversal of this DAG that computes the value for each node (subproblem) based on the values of its predecessors, guaranteeing that each subproblem is solved only once.
In our next lesson, we will move from identifying these properties to the first step of implementation: modeling a problem by defining its state representation and recurrence relation.