101
0/276
Loading content...
A master chef doesn't see a complex dish—they see a sequence of simpler preparations. A skilled architect doesn't see a skyscraper—they see modular components assembled in precise order. And a Dynamic Programming expert doesn't see an overwhelming optimization problem—they see it as a collection of smaller, interrelated subproblems waiting to be solved.
This ability to decompose complex problems into simpler subproblems is the single most important skill in Dynamic Programming. It's both an art and a science—requiring intuition developed through practice and rigorous thinking to verify correctness.
In this page, we'll develop your ability to see problems through the lens of decomposition, transforming monolithic challenges into manageable pieces.
By the end of this page, you will understand how to identify subproblems within larger problems, how to express solutions recursively, and how DP leverages this decomposition to achieve efficiency. You'll learn to ask the right questions that reveal subproblem structure.
A subproblem is a smaller instance of the same type of problem we're trying to solve. It has the same structure, the same kind of input, and the same kind of output—just with 'less' input in some meaningful sense.
Formal definition:
Given a problem P on input X, a subproblem is a problem P' that is structurally identical to P but operates on a smaller or simpler input X' ⊆ X.
Key characteristics of useful subproblems:
Self-similarity — The subproblem has the same form as the original. 'Find shortest path from A to C' has subproblems like 'Find shortest path from B to C'—same type, smaller scope.
Reduction — The subproblem is strictly 'smaller' in some measurable way. This could mean fewer elements, smaller values, shorter strings, or restricted range.
Independence — The subproblem can be solved without knowledge of the original problem's context (we only need its optimal solution, not how it connects to larger problems).
Combinability — Solutions to subproblems can be combined to solve the original problem through some well-defined operation.
Compute F(n) — the nth Fibonacci numberF(n) = F(n-1) + F(n-2)The original problem: Compute F(5)
Subproblems identified:
Why this works:
When facing any DP problem, ask: 'If I knew the optimal solution to all smaller versions of this problem, how would I compute the solution to the current problem?' The answer reveals your subproblem structure.
Breaking problems into subproblems requires recursive thinking—the ability to define a solution in terms of itself applied to smaller inputs. This mindset is fundamental to DP.
The recursive structure of thought:
Assume you've solved smaller instances — This is the 'recursive leap of faith'. Trust that if you can solve the problem for input size n-1, size n-2, etc., those solutions are available.
Focus on the decision at the current level — What choice must you make NOW? What are your options? This single decision, combined with optimal subproblem solutions, should yield the optimal overall solution.
Define the combination rule — How do you merge subproblem solutions with your current decision to get the answer?
Establish base cases — When is the problem small enough to solve directly without further recursion?
The recursive definition template:
SOLUTION(problem) =
if (problem is base case):
return direct_answer
else:
make all possible choices
for each choice:
result = (cost of choice) + SOLUTION(resulting subproblem)
return optimal result among all choices
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051
# Example: Climbing Stairs# You can climb 1 or 2 steps at a time. How many ways to reach step n? def climb_stairs_recursive(n): """ Recursive thinking in action: 1. Assume we know how to reach steps n-1 and n-2 2. Current decision: take 1 step or 2 steps? 3. Combination: ways(n) = ways(n-1) + ways(n-2) - If we take 1 step from n-1, we reach n - If we take 2 steps from n-2, we reach n - These are the ONLY two ways to arrive at n 4. Base cases: ways(0) = 1 (one way: do nothing), ways(1) = 1 """ if n <= 1: return 1 return climb_stairs_recursive(n - 1) + climb_stairs_recursive(n - 2) # Example: Minimum Path Sum in Grid# Given a grid of costs, find minimum cost to go from top-left to bottom-right# You can only move right or down. def min_path_sum_recursive(grid, row, col): """ Recursive thinking in action: 1. Assume we know min paths to cells (row-1, col) and (row, col-1) 2. Current decision: did we arrive from above or from the left? 3. Combination: min_path(row, col) = grid[row][col] + min( min_path(row-1, col), # came from above min_path(row, col-1) # came from left ) 4. Base cases: - min_path(0, 0) = grid[0][0] # starting cell - Out of bounds = infinity (invalid path) """ rows, cols = len(grid), len(grid[0]) # Base cases if row < 0 or col < 0: return float('inf') if row == 0 and col == 0: return grid[0][0] # Recursive case: combine subproblems with current cell cost from_above = min_path_sum_recursive(grid, row - 1, col) from_left = min_path_sum_recursive(grid, row, col - 1) return grid[row][col] + min(from_above, from_left)The hardest part of recursive thinking is trusting that smaller subproblems are already solved. This 'leap of faith' is mathematically justified by induction: if base cases work and the recursive step correctly combines subproblems, the entire solution is correct by induction on problem size.
Every subproblem must be 'smaller' than its parent—but what does 'smaller' mean? Identifying the right dimension of reduction is critical to correct DP formulation.
Common dimensions of reduction:
| Reduction Type | Description | Example Problems |
|---|---|---|
| Index/Position | Reduce array/string by excluding elements from ends | Longest Palindromic Subsequence, Rod Cutting |
| Prefix/Suffix | Consider only first k or last k elements | LCS, Coin Change, Subset Sum |
| Value/Amount | Reduce target value or capacity | Knapsack, Coin Change, Partition Equal Sum |
| Grid Position | Move toward corner (reduce row/col indices) | Unique Paths, Min Path Sum, Edit Distance |
| Subset | Consider subsets of items/elements | Traveling Salesman (bitmask), Partition |
| Range/Interval | Reduce to smaller intervals [i,j] where j-i shrinks | Matrix Chain, Optimal BST, Burst Balloons |
Choosing the right reduction dimension:
The correct dimension depends on the problem's structure. Ask yourself:
What remains constant across the problem? — If you're optimizing over sequences, the sequence structure is constant; you reduce by considering prefixes/suffixes.
What decision reduces the problem? — If choosing an item removes it from consideration, reduce by items. If making a move changes grid position, reduce by position.
What base case makes sense? — The reduction should lead to obvious base cases (empty sequence, zero capacity, corner of grid).
Is the state space polynomial? — If your reduction creates exponentially many distinct states, DP won't help.
s1 = 'ABCDGH', s2 = 'AEDFHR'LCS length = 3 (either 'ADH' or similar)Why prefix reduction works:
Subproblem definition: LCS(i, j) = length of LCS for s1[0..i] and s2[0..j]
Recurrence:
Base case: LCS(0, j) = LCS(i, 0) = 0 (empty prefix has LCS 0)
State space: O(m × n) — polynomial ✓
Some problems seem to have subproblem structure but lead to exponential state spaces. For example, 'all subsets' as states gives 2ⁿ subproblems—too many unless n is very small (~20). Always verify that your chosen reduction yields polynomial states.
Subproblems have dependencies: solving one subproblem requires solutions to others. These dependencies form a Directed Acyclic Graph (DAG) — directed because dependencies have direction, acyclic because well-formed subproblems never depend on themselves (that would be circular and unsolvable).
Visualizing the subproblem DAG:
Consider Fibonacci: F(5) depends on F(4) and F(3). F(4) depends on F(3) and F(2). This creates a dependency graph:
Properties of the subproblem DAG:
Base cases are sources — Nodes with no incoming edges (F(0), F(1)). These must be solvable directly.
The answer is a sink — The main problem we want to solve (F(5)). This has no outgoing edges.
Edges represent dependencies — An edge from A to B means 'solving B requires solution to A'.
Topological order reveals computation order — We must solve subproblems before problems that depend on them.
Why acyclicity matters:
If the graph had cycles (A depends on B, B depends on A), we'd have no valid starting point—an infinite loop with no solution. Valid DP problems always have acyclic dependency graphs.
Recognizing the DAG helps with:
View DP as traversing the subproblem DAG: start from sources (base cases), follow edges (compute dependent subproblems), until you reach the sink (the answer). Top-down DP explores the DAG demand-driven (DFS from sink). Bottom-up DP explores it supply-driven (BFS from sources).
After solving many DP problems, you'll recognize recurring subproblem patterns. These patterns serve as templates for new problems, accelerating your problem-solving process.
Pattern 1: Linear DP — Single Sequence
Subproblem: dp[i] = solution considering elements 0 to i (or i to n-1)
Examples: Climbing Stairs, House Robber, Maximum Subarray, Longest Increasing Subsequence
dp[i] = optimal solution for subproblem ending at or using index i
Recurrence: dp[i] = f(dp[i-1], dp[i-2], ..., arr[i])
Base: dp[0] = initial_value
Pattern 2: Linear DP — Two Sequences
Subproblem: dp[i][j] = solution considering first i elements of seq1 and first j elements of seq2
Examples: Longest Common Subsequence, Edit Distance, String Interleaving
dp[i][j] = optimal solution for prefixes seq1[0..i-1] and seq2[0..j-1]
Recurrence: dp[i][j] = f(dp[i-1][j], dp[i][j-1], dp[i-1][j-1], seq1[i], seq2[j])
Base: dp[0][j] = dp[i][0] = boundary_values
Pattern 3: Knapsack-style DP
Subproblem: dp[i][w] = solution considering first i items with capacity/budget w
Examples: 0/1 Knapsack, Subset Sum, Coin Change, Partition Equal Sum
dp[i][w] = optimal solution for items 0..i-1 with capacity w
Recurrence: dp[i][w] = optimal(dp[i-1][w], value[i] + dp[i-1][w-weight[i]])
Base: dp[0][w] = 0 (no items = no value)
Pattern 4: Interval DP
Subproblem: dp[i][j] = solution for the interval/subarray from index i to j
Examples: Matrix Chain Multiplication, Optimal BST, Burst Balloons, Palindrome Partitioning
dp[i][j] = optimal solution for interval [i, j]
Recurrence: dp[i][j] = optimal over all split points k in [i, j-1] of
f(dp[i][k], dp[k+1][j], merge_cost)
Base: dp[i][i] = single_element_solution
Pattern 5: Grid DP
Subproblem: dp[i][j] = solution for reaching cell (i, j) from origin
Examples: Unique Paths, Minimum Path Sum, Maximal Square, Dungeon Game
dp[i][j] = optimal solution for cell (i, j)
Recurrence: dp[i][j] = f(dp[i-1][j], dp[i][j-1], grid[i][j])
Base: dp[0][0] = start_value, first row/col = accumulated values
| Pattern | State Definition | State Space | Dependency Direction |
|---|---|---|---|
| Linear (1D) | dp[i] | O(n) | Left to right or right to left |
| Two Sequence (2D) | dp[i][j] | O(m × n) | Diagonal fill or row-by-row |
| Knapsack (2D) | dp[i][w] | O(n × W) | Row-by-row, use previous row |
| Interval (2D) | dp[i][j] | O(n²) | By interval length, increasing |
| Grid (2D) | dp[i][j] | O(m × n) | Top-left to bottom-right |
When you encounter a new problem, try to match it to a known pattern. 'This looks like a two-sequence comparison problem' → think LCS-style dp[i][j]. 'This involves choosing items with a budget' → think Knapsack-style dp[i][w]. Pattern matching gives you a head start.
Defining subproblems is the creative core of DP. Here's a systematic process to guide your thinking:
Step 1: Understand the original problem completely
Before decomposing, ensure you understand:
Step 2: Identify what makes the problem 'big'
What aspect of the input makes it complex?
Step 3: Consider what a 'smaller' version looks like
If you removed one element, reduced the target, or considered a prefix—what would the smaller problem be? Is it the same TYPE of problem?
Step 4: Define the state precisely
The state captures all information needed to solve a subproblem. Ask:
Step 5: Write the recurrence (informally first)
Express how the current state relates to smaller states. Use words before equations:
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354
"""Walkthrough: House Robber Problem Problem: You're a robber. Houses are in a line. Each house has money.You can't rob adjacent houses (alarm systems). Maximize money stolen. Input: nums = [2, 7, 9, 3, 1]Output: Maximum money = 12 (rob houses with 2, 9, 1)""" # Step 1: Understand the problem# - Input: array of non-negative integers (money in each house)# - Output: maximum total money# - Constraint: can't take from adjacent indices # Step 2: What makes it 'big'?# - The length of the array (n houses) # Step 3: What's a 'smaller' version?# - Consider only the first k houses (prefix)# - This is the SAME problem, just smaller # Step 4: Define the state# - dp[i] = maximum money we can steal from houses 0 to i# - The 'i' parameter uniquely identifies the subproblem # Step 5: Write the recurrence (thinking out loud)# - For house i, we have two choices:# a) Rob house i: we get nums[i], but can't use nums[i-1]# So we add nums[i] to dp[i-2] (best up to 2 houses back)# b) Skip house i: we keep dp[i-1] (best without house i)# - dp[i] = max(dp[i-1], nums[i] + dp[i-2]) # Step 6: Base cases# - dp[0] = nums[0] (only one house, rob it)# - dp[1] = max(nums[0], nums[1]) (two houses, pick better one) def rob(nums): if not nums: return 0 if len(nums) == 1: return nums[0] n = len(nums) dp = [0] * n dp[0] = nums[0] dp[1] = max(nums[0], nums[1]) for i in range(2, n): dp[i] = max(dp[i-1], nums[i] + dp[i-2]) return dp[n-1] # Result: rob([2, 7, 9, 3, 1]) = 12Once you correctly define what dp[...] represents, the recurrence often becomes obvious. Spend 70% of your thinking time on state definition, 30% on the recurrence. A well-defined state makes the solution almost write itself.
Defining subproblems incorrectly leads to subtle bugs that are hard to detect. Here's how to verify your subproblem structure is correct:
Check 1: Completeness — Do subproblems cover all possibilities?
Your recurrence should consider ALL ways to reach the current state. If you miss a case, your solution may be suboptimal.
Example bug: In House Robber, if you only consider robbing the current house (and forget the 'skip' option), you'll miss the optimal solution when skipping is better.
Check 2: Base cases handle all boundary conditions
Your recursion will eventually hit the smallest cases. Ensure:
Example bug: Forgetting the n=1 case in Climbing Stairs causes an array index error.
Check 3: Subproblems are strictly smaller
Every recursive call must reduce the problem size. If any call maintains or increases size, you have infinite recursion.
Example bug: dp[i] = dp[i] + 1 causes infinite recursion.
Check 4: No circular dependencies
Subproblems should form a DAG. If A depends on B and B depends on A, you can't solve either.
Example bug: dp[i] = dp[i+1] - 1 combined with bottom-up iteration that assumes dp[i+1] isn't yet computed.
The best verification is testing. Manually trace your recurrence for n=0, 1, 2, 3. Compute by hand. If the recurrence gives wrong answers for small cases, it will give wrong answers for large cases. Small-case testing catches most subproblem definition errors.
Breaking problems into subproblems is the foundational skill of Dynamic Programming. Let's consolidate what we've learned:
What's next:
We've seen how to decompose problems into subproblems. But subproblem overlap is what makes DP efficient—without it, we'd just have divide-and-conquer. The next page explores how we store solutions to avoid recomputation, the mechanism that transforms exponential recursion into polynomial-time algorithms.
You now understand how to decompose complex problems into subproblems. You've learned the recursive mindset, common patterns, and verification techniques. Next, we'll explore memoization and tabulation—the storage mechanisms that make DP efficient.