OneNoughtOne
0/361
Loading content...
Read aloud is unavailable in this browser.
Dynamic Programming is universally regarded as one of the most challenging topics in computer science education. Yet the fundamental difficulty isn't in implementing DP solutions—it's in recognizing when DP applies in the first place. This recognition skill separates engineers who struggle with DP from those who wield it effortlessly.
Consider this: given a completely new problem, how do you know whether to use DP, greedy algorithms, divide-and-conquer, or brute-force search? The answer isn't intuition—it's pattern recognition built on a deep understanding of DP's fundamental requirements.
This page provides you with a systematic framework for identifying DP problems. By the end, you'll possess a mental checklist that transforms the question 'Is this a DP problem?' from a guess into a methodical analysis.
By completing this page, you will be able to:
• Identify the two fundamental properties that define DP problems • Recognize common linguistic and structural patterns that signal DP • Distinguish DP problems from greedy and divide-and-conquer problems • Apply a systematic checklist to evaluate any optimization problem
At its core, Dynamic Programming is applicable when a problem exhibits exactly two properties. These properties are not optional enhancements—they are necessary and sufficient conditions for DP to provide benefit over other approaches.
Understanding these properties deeply is the single most important skill for DP problem identification. Let's examine each in rigorous detail.
A problem with overlapping subproblems but no optimal substructure cannot be solved with DP. Similarly, a problem with optimal substructure but no overlapping subproblems may be better suited to divide-and-conquer. DP lives at the intersection of both properties.
Why These Properties Matter:
Overlapping Subproblems enables efficiency. When different branches of recursion solve identical subproblems, storing their solutions eliminates redundant computation. Without overlap, every subproblem is unique, and memoization provides no benefit.
Optimal Substructure enables correctness. It guarantees that combining optimal subproblem solutions yields an optimal overall solution. Without this property, we'd need to examine all combinations of subproblem solutions—which is exactly what brute force does.
The magic of DP is that these two properties together allow us to achieve what seems contradictory: exploring all possibilities (via subproblem composition) while avoiding redundant work (via memoization).
Overlapping subproblems occur when a recursive algorithm solves the same subproblem multiple times during its execution. This is fundamentally different from divide-and-conquer algorithms like Merge Sort, where each subproblem is unique.
The Mental Test:
When analyzing a problem, ask yourself: "If I draw the recursion tree, will I see the same function calls with identical parameters appearing in multiple branches?"
If yes, you have overlapping subproblems.
12345678910111213141516171819
// Naive recursive Fibonacci - OVERLAPPING SUBPROBLEMSfunction fib(n: number): number { if (n <= 1) return n; return fib(n - 1) + fib(n - 2);} // Recursion tree for fib(5):// fib(5)// / \// fib(4) fib(3) ← fib(3) appears in both branches// / \ / \// fib(3) fib(2) fib(2) fib(1)// / \// fib(2) fib(1)//// fib(3) is computed 2 times// fib(2) is computed 3 times// fib(1) is computed 5 times// This redundancy grows EXPONENTIALLY with nContrast with Divide-and-Conquer:
In Merge Sort, we also have a recursive structure, but each subproblem is unique—no subarray is sorted twice. This is why Merge Sort doesn't benefit from memoization.
12345678910111213141516171819
// Merge Sort - NO overlapping subproblemsfunction mergeSort(arr: number[], left: number, right: number): void { if (left < right) { const mid = Math.floor((left + right) / 2); mergeSort(arr, left, mid); // Left half mergeSort(arr, mid + 1, right); // Right half merge(arr, left, mid, right); }} // Recursion tree for array [4,1,3,2]:// mergeSort([4,1,3,2])// / \// mergeSort([4,1]) mergeSort([3,2])// / \ / \// mergeSort([4]) mergeSort([1]) mergeSort([3]) mergeSort([2])//// Every subproblem is UNIQUE - no overlap// Memoization would provide ZERO benefitCount the number of unique subproblems. If this number is polynomial (like O(n²) or O(n×W)) while naive recursion is exponential, you have significant overlap. The ratio between exponential branches and polynomial unique states reveals the redundancy that DP eliminates.
Optimal substructure means that an optimal solution to the whole problem can be constructed from optimal solutions to its subproblems. This property is what allows DP to work—we solve subproblems optimally, store those solutions, and combine them to form the global optimum.
The Mental Test:
Suppose you have an optimal solution to the original problem. Can you 'cut' this solution into pieces, and claim that each piece is itself an optimal solution to the corresponding subproblem?
If yes, you have optimal substructure.
The Longest Simple Path problem asks for the longest path between two vertices in a graph without repeating vertices. This problem does NOT have optimal substructure.
Why? Suppose the longest simple path from A to C goes through B. The A→B portion might NOT be the longest simple path from A to B—because a longer A→B path might reuse vertices needed for the B→C portion.
The constraint of 'no repeated vertices' creates dependencies between subproblems that violate optimal substructure. This is why longest simple path is NP-hard while shortest path is polynomial.
Proving Optimal Substructure (Cut-and-Paste Argument):
The standard technique for proving optimal substructure is the cut-and-paste argument:
This proves that OPT must contain optimal subproblem solutions.
1234567891011121314151617181920212223
// THEOREM: Shortest paths have optimal substructure.//// PROOF:// Let P = {v₁, v₂, ..., vₖ} be a shortest path from v₁ to vₖ.// Consider any intermediate vertex vᵢ (1 < i < k).//// CLAIM: The subpath {v₁, ..., vᵢ} is a shortest path from v₁ to vᵢ.//// PROOF BY CONTRADICTION:// Suppose there exists a shorter path Q from v₁ to vᵢ.// // Then we could construct a new path P' by:// P' = Q + {vᵢ, vᵢ₊₁, ..., vₖ}//// The length of P' = length(Q) + length({vᵢ, ..., vₖ})// < length({v₁, ..., vᵢ}) + length({vᵢ, ..., vₖ})// = length(P)//// But this contradicts our assumption that P is shortest!// Therefore, {v₁, ..., vᵢ} must be a shortest path from v₁ to vᵢ.//// By symmetric argument, {vᵢ, ..., vₖ} is shortest from vᵢ to vₖ.// ∎Beyond the formal properties, certain linguistic patterns in problem statements strongly suggest DP. While these aren't foolproof indicators, they're reliable heuristics that experienced engineers use for rapid problem classification.
Learning to recognize these patterns accelerates your problem-solving significantly.
| Pattern | What It Suggests | Example Problems |
|---|---|---|
| "Count the number of ways..." | Counting problems with overlapping paths | Climbing stairs, unique paths, coin change combinations |
| "Find the minimum/maximum..." | Optimization requiring all possibilities | Minimum edit distance, maximum profit, shortest path |
| "Is it possible to..." | Decision problems often reducible to counting | Subset sum, word break, partition equal subset |
| "Find the longest/shortest..." | Sequence optimization problems | LCS, LIS, longest palindromic subsequence |
| "Given a sequence/string/array..." | Linear or 2D subproblem structure | Most string and sequence DP problems |
| "...using at most k operations" | State includes remaining budget/capacity | Edit distance with bounded operations, buying/selling with k transactions |
| "...partition into groups..." | Subset/partition problems | Partition array, balanced partition, k-sum |
Just because a problem says 'find the minimum' doesn't guarantee DP is the right approach. Greedy algorithms also optimize, and BFS finds shortest paths in unweighted graphs. These patterns raise your DP antenna—but you must still verify the two fundamental properties.
Structural Patterns:
Beyond language, certain problem structures are DP signatures:
• Sequence-to-goal problems: Get from state A to state B with some constraint (climbing stairs, coin change) • Two-sequence comparison: Compare strings/arrays and find relationships (LCS, edit distance) • Interval problems: Find optimal way to handle ranges (matrix chain, burst balloons) • Decision at each step: Include/exclude, go left/right, take/skip (knapsack, house robber) • Grid traversal with constraints: Navigate a 2D grid optimally (unique paths, minimum path sum)
One of the most common sources of confusion is distinguishing when to use DP versus greedy algorithms or divide-and-conquer. All three paradigms share similarities—they all decompose problems into smaller pieces. The critical differences lie in how subproblems relate and whether local decisions guarantee global optimality.
| Property | Dynamic Programming | Greedy | Divide & Conquer |
|---|---|---|---|
| Subproblems | Overlapping (same subproblem solved multiple times) | Usually single path (each choice leads to one subproblem) | Non-overlapping (each subproblem is unique) |
| Decision process | Consider all options, combine optimally | Make locally optimal choice, never reconsider | Divide independently, combine results |
| Correctness guarantee | Explores all combinations via subproblems | Requires proof that greedy choice is safe | Correct by complete exploration of partitions |
| Example | 0/1 Knapsack (must consider all subsets) | Activity Selection (earliest end time works) | Merge Sort (each subarray sorted independently) |
Coin Change is the perfect example of why greedy fails and DP is needed.
With coins [1, 3, 4], make amount 6: • Greedy (largest first): 4 + 1 + 1 = 3 coins • DP (optimal): 3 + 3 = 2 coins
Greedy fails because taking the largest coin now prevents a better combination later. This 'future dependency' is the hallmark of DP problems.
Key Insight:
When greedy works, it's always preferable (simpler, faster). DP is the fallback when greedy fails. The experienced engineer's approach:
Let's synthesize everything into a practical, step-by-step checklist you can apply to any problem. This checklist transforms DP recognition from an art into a systematic process.
12345678910111213141516171819202122232425262728293031323334353637
// PROBLEM: Given string s and dictionary wordDict, return true if s can be// segmented into a space-separated sequence of dictionary words.//// Example: s = "leetcode", wordDict = ["leet", "code"] → true // CHECKLIST APPLICATION://// 1. TRIGGER PHRASES: "Is it possible to..." → Decision problem ✓//// 2. DECISION STRUCTURE: At each position, we choose which word starts there.// Multiple words might fit. We can't easily determine which choice is "best"// without trying them. → Suggests DP ✓//// 3. SUBPROBLEM DEFINITION: // canBreak(i) = "Can we segment s[i...n-1]?"// Parameter: i (starting index)//// 4. OVERLAPPING SUBPROBLEMS?// If s = "aaaaab", dict = ["a", "aa", "aaa"]// canBreak(3) might be reached from:// - canBreak(0) → "aaa" → canBreak(3)// - canBreak(0) → "aa" → canBreak(2) → "a" → canBreak(3)// - canBreak(0) → "a" → canBreak(1) → "aa" → canBreak(3)// Same subproblem via multiple paths! → Overlap ✓//// 5. OPTIMAL SUBSTRUCTURE?// If whole string is breakable, and we use word w at position i,// then remaining string s[i+len(w)...] must also be breakable.// If remaining weren't breakable, whole wouldn't be. → Optimal substructure ✓//// 6. GREEDY? No obvious greedy choice. Longest match first? Fails.// "catsandog" with ["cats", "and", "dog", "cat", "sand"] - // "cats" first leads to failure, "cat" first succeeds. → Need DP ✓//// 7. SUBPROBLEM COUNT: O(n) unique subproblems (one for each starting index)//// CONCLUSION: DP is appropriate!The checklist becomes second nature with practice. After solving 50+ DP problems, you'll instinctively recognize patterns without explicitly running through each step. But the checklist remains valuable for unfamiliar problem types and for explaining your reasoning to others.
Most DP problems fall into a handful of well-known categories. Recognizing which category a problem belongs to dramatically accelerates your solution design, as each category has established state definitions and transition patterns.
| Category | State Typically Tracks | Example Problems |
|---|---|---|
| Linear Sequence (1D) | Current index or position | Climbing Stairs, House Robber, Max Subarray |
| Two Sequences (2D) | Position in each sequence | LCS, Edit Distance, Regular Expression Matching |
| Grid Traversal (2D) | Current row and column | Unique Paths, Minimum Path Sum, Dungeon Game |
| Knapsack Variants | Index + remaining capacity | 0/1 Knapsack, Coin Change, Subset Sum |
| Interval DP | Start and end of interval | Matrix Chain Multiplication, Burst Balloons, Palindrome Partitioning |
| Tree DP | Current node + state at node | Binary Tree Maximum Path Sum, Tree Diameter, House Robber III |
| State Machine DP | Index + current state (e.g., holding/not holding) | Best Time to Buy and Sell Stock series |
| Digit DP | Position + constraints + tight bound | Count numbers with properties, Numbers with no consecutive 1s |
| Bitmask DP | Subset represented as bitmask | Traveling Salesman, Assignment Problem, Shortest Superstring |
Using Categories for Recognition:
When you encounter a new problem, ask: "Which category does this resemble?"
• Two strings being compared? → Two Sequences (2D) • Navigating a grid? → Grid Traversal • Selecting items with a capacity constraint? → Knapsack • Finding optimal way to process an interval? → Interval DP • Tracking which elements have been used? → Bitmask DP
Categorization provides a starting template. You'll often need to adapt the template, but having a foundation accelerates your problem-solving significantly.
Many problems combine multiple categories. For example, 'Minimum Cost to Merge Stones' is both Interval DP (processing ranges) and has Knapsack-like constraints (merge exactly k piles). Recognizing each component helps you design a state that captures all relevant information.
Just as important as recognizing DP problems is recognizing when DP is NOT the appropriate tool. Attempting to force DP onto unsuitable problems wastes time and leads to unnecessarily complex solutions.
Sometimes you define a 'state' that seems reasonable but has exponential many unique values. For example, if your state is 'the set of elements used so far,' there are 2ⁿ possible sets—DP degrades to brute force.
Exception: Bitmask DP deliberately uses exponential states but works for small n (typically n ≤ 20). Know your problem's constraints!
Alternative Approaches When DP Doesn't Fit:
• Greedy: When local optimal choices lead to global optimum (Activity Selection, Huffman Coding) • Divide-and-Conquer: When subproblems are unique and independent (Merge Sort, Quick Select) • Backtracking: When you need to enumerate solutions or subproblem count is exponential (N-Queens, Sudoku) • Graph Algorithms: When the problem structure is naturally a graph (BFS for unweighted shortest path, Dijkstra for weighted) • Mathematical/Closed-form: When a formula directly computes the answer (Catalan numbers, combinatorics)
Let's solidify your understanding with practice problems. For each problem below, apply the recognition checklist and determine whether DP applies, identify the category if so, or suggest an alternative if not.
123456789101112131415
// PROBLEM: Given a circular integer array nums, return the maximum // possible sum of a non-empty subarray of nums.// A circular array means the end connects to the beginning. // YOUR ANALYSIS:// 1. Trigger phrases? "Maximum possible sum" → Optimization ✓// 2. Decision structure? Choose start and end positions// 3. Subproblem? maxSum ending at position i// 4. Overlapping? Check if same subproblem appears multiple times// 5. Optimal substructure? Does max circular contain max of subparts?// 6. Greedy alternative? Consider Kadane's algorithm variant//// ANSWER: This is a DP problem (variant of Maximum Subarray).// The circular constraint adds complexity but doesn't break DP applicability.// Key insight: max circular sum = max(maxKadane, totalSum - minKadane)12345678910111213
// PROBLEM: Given an integer array nums of unique elements, // return ALL possible subsets (the power set). // YOUR ANALYSIS:// 1. Trigger phrases? "All possible" → Enumeration, not optimization// 2. This asks to OUTPUT all solutions, not count them// 3. Subproblem count? 2^n subsets - exponential// 4. Can DP help here?//// ANSWER: This is NOT a DP problem.// DP optimizes by avoiding recomputation, but here we need all solutions.// Use BACKTRACKING to enumerate all subsets.// Time complexity is inherently O(2^n) since we output 2^n subsets.1234567891011121314
// PROBLEM: Given an array nums where nums[i] represents maximum jump // length from position i, return minimum number of jumps to reach the end.// You can assume you can always reach the end. // YOUR ANALYSIS:// 1. Trigger phrases? "Minimum number of" → Optimization ✓// 2. Decision structure? At each position, choose jump length// 3. Subproblem? minJumps(i) = min jumps to reach end from i// 4. Overlapping? Same position i can be reached via different paths// 5. Optimal substructure? Min from current = 1 + min from where we land//// ANSWER: DP works! O(n²) solution with state = current index.// BUT: Greedy also works here (always jump to position giving max reach).// Greedy gives O(n) solution. Prefer greedy when provable!The exercises illustrate three scenarios:
Always consider alternatives before committing to DP!
We've covered the essential framework for identifying Dynamic Programming problems. Let's consolidate the key insights:
What's Next:
Recognizing a DP problem is only the first step. The next page covers Defining State and Transitions—the heart of DP solution design. We'll learn how to translate problem understanding into precise mathematical formulations that lead directly to implementation.
You now have a systematic framework for identifying Dynamic Programming problems. With practice, this recognition becomes instinctive—you'll 'see' the DP structure in problems just as an experienced chess player sees tactical patterns on the board. Next, we'll master the art of defining states and transitions.