Introduction to Dynamic Programming
What is Dynamic Programming?
Dynamic Programming (DP) is a method for solving complex problems by breaking them down into simpler subproblems. It is applicable when the problem has overlapping subproblems and optimal substructure.
Where to Use Dynamic Programming?
DP is commonly used in optimization problems, such as:
- Finding shortest paths in graphs
- Sequence alignment in bioinformatics
- Resource allocation problems
- Knapsack and other combinatorial optimization problems
- Game theory and decision making
How to Use Dynamic Programming?
1
Identify Subproblems
Break down the main problem into smaller, overlapping subproblems.
2
Define Recurrence Relation
Express the solution of the main problem in terms of solutions to subproblems.
3
Implement Memoization/Tabulation
Store solutions to subproblems to avoid redundant calculations.
4
Construct Solution
Use stored solutions to build the solution to the original problem.
DP Parent Problems
These are the fundamental DP problems that form the basis for many variations. Mastering these will help you solve a wide range of DP challenges.
🧠1. Fibonacci / Linear Recurrence DP
Parent Concept: Problems where each state depends on one or more previous states.
dp[i] = dp[i-1] + dp[i-2]
LeetCode #509 - Fibonacci Number
💰 2. Knapsack (0/1 and Unbounded)
Parent Concept: Problems where you must select items under capacity/limit constraints to maximize or minimize a result.
dp[i][j] = max(dp[i-1][j], value[i] + dp[i-1][j-weight[i]])
LeetCode #416 - Partition Equal Subset Sum
🔠3. Longest Common Subsequence (LCS)
Parent Concept: Compare two sequences and find relationships between their prefixes.
dp[i][j] = 1 + dp[i-1][j-1] if match, else max(dp[i-1][j], dp[i][j-1])
LeetCode #1143 - Longest Common Subsequence
🧱 4. Grid / Matrix DP
Parent Concept: Move inside a 2D grid (top-down or left-right) to compute paths or minimal costs.
dp[i][j] = cell[i][j] + min(dp[i-1][j], dp[i][j-1])
LeetCode #62 - Unique Paths
🧩 5. Subsequence / LIS (Longest Increasing Subsequence)
Parent Concept: Choose elements in a sequence that follow an order or relation (increasing, arithmetic, etc.)
dp[i] = max(dp[j] + 1) for all j < i satisfying condition
LeetCode #300 - Longest Increasing Subsequence
💫 6. Partition DP / Matrix Chain Multiplication (MCM)
Parent Concept: Divide a sequence into subproblems (choose partition boundaries) to minimize cost.
dp[i][j] = min(dp[i][k] + dp[k+1][j] + cost[i][j])
LeetCode #312 - Burst Balloons
🌳 7. DP on Trees
Parent Concept: Compute results bottom-up on tree structure using postorder traversal.
dp[node] = combine(dp[left], dp[right])
LeetCode #543 - Diameter of Binary Tree
🧠8. DP on Graphs
Parent Concept: Compute shortest/longest paths or path counts in a DAG or weighted graph using topological order or memoization.
Shortest Path in DAG (classical base problem)
LeetCode #847 - Shortest Path Visiting All Nodes
🔢 9. Bitmask DP
Parent Concept: Represent subsets or visited states using bitmasking; used in combinatorial search + optimization problems.
dp[mask][i] = min(dp[mask ^ (1 << i)][j] + cost[j][i])
LeetCode #847 - Shortest Path Visiting All Nodes
🔟 10. Digit DP
Parent Concept: Count or calculate results based on the digits of a number under certain constraints.
dp[pos][tight][mask]
LeetCode #357 - Count Numbers with Unique Digits
All DP Variation Problems
These problems are variations of the parent DP problems. Understanding the connections helps in recognizing patterns and applying solutions effectively.
| Problem | Description | LeetCode |
|---|---|---|
| Fibonacci / Linear Recurrence Variations | ||
| Climbing Stairs | Number of ways to climb n stairs (1 or 2 steps) | #70 |
| Min Cost Climbing Stairs | Cost attached to each stair | #746 |
| House Robber | Max sum without adjacent elements | #198 |
| House Robber II | Circular arrangement | #213 |
| Decode Ways | Count valid string decodings | #91 |
| Knapsack / Subset / Coin Change Variations | ||
| Partition Equal Subset Sum | Check if array can be partitioned into two subsets with equal sum | #416 |
| Target Sum | +/- to reach target | #494 |
| Last Stone Weight II | Partition difference minimization | #1049 |
| Coin Change | Minimum coins to reach amount | #322 |
| Coin Change II | Count combinations to form sum | #518 |
| LCS / String Matching Variations | ||
| Edit Distance | Minimum operations to convert strings | #72 |
| Delete Operation for Two Strings | Deletions to equalize strings | #583 |
| Minimum ASCII Delete Sum | Weighted variant | #712 |
| Longest Palindromic Subsequence | LCS of s and reverse(s) | #516 |
| Grid / Matrix DP Variations | ||
| Unique Paths II | Grid with obstacles | #63 |
| Minimum Path Sum | Min cost path | #64 |
| Dungeon Game | Minimum health required | #174 |
| Minimum Falling Path Sum | From top to bottom | #931 |
| LIS / Subsequence Variations | ||
| Russian Doll Envelopes | 2D LIS variant | #354 |
| Maximum Length of Pair Chain | Pair-based LIS | #646 |
| Number of Longest Increasing Subsequences | Count LIS | #673 |
| Longest Arithmetic Subsequence | Maintain difference state | #1027 |
| Partition DP / MCM Variations | ||
| Burst Balloons | Max coins by choosing partition order | #312 |
| Palindrome Partitioning II | Min cuts to form palindromes | #132 |
| Minimum Score Triangulation | Polygon DP | #1039 |
| Minimum Cost to Cut a Stick | Sort and partition cost | #1547 |
| Tree DP Variations | ||
| Binary Tree Maximum Path Sum | Max path sum in binary tree | #124 |
| House Robber III | Tree version of house robber | #337 |
| Longest Univalue Path | Same value path | #687 |
| Bitmask DP Variations | ||
| Shortest Path Visiting All Nodes | TSP variant | #847 |
| Partition to K Equal Sum Subsets | Subset masking | #698 |
| Matchsticks to Square | DP over subsets | #473 |
Core DP Patterns
Understanding these core patterns will help you recognize which DP approach to apply to new problems.
Linear Recurrence
Each state depends on one or more previous states. Examples: Fibonacci, Climbing Stairs, House Robber.
Knapsack
Select items under constraints to optimize value. Examples: 0/1 Knapsack, Coin Change, Subset Sum.
LCS
Compare two sequences to find relationships. Examples: LCS, Edit Distance, String Matching.
Grid DP
Navigate 2D grids to find optimal paths. Examples: Unique Paths, Minimum Path Sum.
LIS
Find ordered subsequences in a sequence. Examples: LIS, Russian Doll Envelopes.
Partition DP
Divide sequences optimally. Examples: MCM, Burst Balloons, Palindrome Partitioning.
Tree DP
Compute results on tree structures. Examples: Diameter of Tree, Max Path Sum.
Bitmask DP
Represent subsets using bitmasks. Examples: TSP, Partition Problems.
Digit DP
Count numbers with digit constraints. Examples: Count Numbers with Unique Digits.
Summary of Core Patterns
| Category | Parent Problem | Common Variations |
|---|---|---|
| Linear Recurrence | Fibonacci | Climb Stairs, Robber, Decode Ways |
| Knapsack | 0/1 Knapsack | Coin Change, Subset Sum |
| LCS | LCS | Edit Distance, Subsequence |
| Grid | Unique Paths | Minimum Path Sum, Triangle |
| LIS | LIS | Russian Dolls, Bitonic |
| Partition | MCM | Burst Balloons, Palindrome Partition |
| Tree | Diameter | Max Path, Robber III |
| Bitmask | TSP | Equal Subsets, Connect Groups |