Dynamic Programming
The Dynamic Programming Pattern
Solve each distinct subproblem once and reuse the answer. Memoization caches results on top of the natural recursion; tabulation fills a table bottom-up. Both depend on finding a recurrence that expresses a problem in terms of smaller versions of itself.
Interactive problems
Free to open
How do you recognise a dynamic programming problem?
The problem asks for a count of ways, a minimum or maximum over choices, or whether something is achievable — and a brute-force recursion would solve the same subproblem repeatedly. Overlapping subproblems plus optimal substructure is the signature.
What is the time complexity of the dynamic programming pattern?
Usually O(states × transitions). A 1D DP over n items is O(n); knapsack and most string DP are O(n × m). Space often reduces to one or two rows.
Dynamic Programming practice problems
Each problem pairs a worked explanation with an interactive visualizer you step through yourself, plus the implementation in JavaScript, Python, Java and C++.
Dynamic Programming problems by difficulty and complexity
The difficulty, running time and extra space of every dynamic programming solution on this page, as each lesson derives them.
| Lesson | Difficulty | Best | Average | Worst | Space |
|---|---|---|---|---|---|
| Intro to Dynamic Programming | Medium | Ω(n) | Θ(n) | O(n) | O(n) |
| Solving a Question with DP | Medium | Ω(n) | Θ(n) | O(n) | O(n) |
| Counting Bits | Easy | Ω(n) | Θ(n) | O(n) | O(1) |
| House Robber | Medium | Ω(n) | Θ(n) | O(n) | O(n) |
| House Robber II | Medium | Ω(n) | Θ(n) | O(n) | O(1) |
| Coin Change | Medium | Ω(amount · k) | Θ(amount · k) | O(amount · k) | O(amount) |
| Decode Ways | Medium | Ω(n) | Θ(n) | O(n) | O(n) |
| Maximal Square | Medium | Ω(m · n) | Θ(m · n) | O(m · n) | O(m · n) |
| Unique Paths | Medium | Ω(m · n) | Θ(m · n) | O(m · n) | O(m · n) |
| Longest Increasing Subsequence | Medium | Ω(n²) | Θ(n²) | O(n²) | O(n) |
| Word Break | Medium | Ω(n) | Θ(n² · k) | O(n² · k) | O(n + d) |
| Maximum Profit in Job Scheduling | Hard | Ω(n log n) | Θ(n log n) | O(n log n) | O(n) |
Related patterns and concepts
The underlying technique is covered from first principles in the dynamic programming lesson in the DSA visualizer curriculum. Dynamic Programming is one of the 17 coding interview patterns, and its problems also appear in the DSA 75 interview sprint.
Every other coding interview pattern
Depth-First Search · 25 lessons
- Introduction to DFSFree
- DFS FundamentalsFree
- Return Values in DFS
- Invert Binary Tree
- Maximum Depth of Binary Tree
- Path Sum
- Passing Values Down (State)
- Validate Binary Search Tree
- Kth Smallest Element in a BST
- Construct Binary Tree from Preorder and Inorder Traversal
- Binary Tree Tilt
- Diameter of Binary Tree
- Lowest Common Ancestor of a Binary Tree
- Path Sum II
- Longest Univalue Path
- Graphs Overview
- Graph Representation: Adjacency List
- Clone Graph
- Graph Valid Tree
- Matrices as Graphs
- Flood Fill
- Types of DFS (Tree Traversals)
- Number of Islands
- Surrounded Regions
- Pacific Atlantic Water FlowFree