Dynamic Programming
Dynamic Programming, Step by Step
Dynamic programming is where most interview preparation stalls. The obstacle is rarely the code, which is usually short — it is seeing the recurrence, and recognising that a problem has overlapping subproblems in the first place.
These lessons approach DP as a progression rather than a collection of solutions. You start from plain recursion, watch the same subproblem get recomputed, add memoization and see the recomputation disappear, then flip to tabulation and watch the table fill. Working through the classic families — knapsack, sequence, string and tree DP — turns them into recognisable shapes instead of separate problems to memorise.
Interactive lessons
Free to open
Languages (JS, TS, Python, Java, C, C++)
Dynamic Programming lessons
Dynamic Programming time and space complexity compared
Best, average and worst-case running time and extra space for every dynamic programming lesson, as each lesson derives them.
| Lesson | Best | Average | Worst | Space |
|---|---|---|---|---|
| Introduction | Variable | Variable | Variable (Depends on State Space) | Variable (Usually O(State Space)) |
| Fibonacci Sequence | O(N) | O(N) | O(N) (vs O(2^N) for naive recursion) | O(N) (Can be optimized to O(1) space) |
| Climbing Stairs | O(N) | O(N) | O(N) | O(N) (Optimizable to O(1)) |
| Unique Paths | O(m*n) | O(m*n) | O(m*n) | O(m*n) (Can be optimized to O(n) or O(min(m,n))) |
| 0/1 Knapsack | O(N*W) | O(N*W) | O(N*W) | O(N*W) (Optimizable to O(W)) |
| Subset Sum | O(N*Target) | O(N*Target) | O(N*Target) | O(N*Target) (Optimizable to O(Target)) |
| Longest Common Subsequence | O(M*N) | O(M*N) | O(M*N) | O(M*N) |
| Longest Increasing Subsequence | Ω(N²) | Θ(N²) | O(N²) | O(N) |
| Edit Distance | O(M*N) | O(M*N) | O(M*N) | O(M*N) |
| Max Path Sum | O(N) | O(N) | O(N) | O(H) (Recursion Stack) |
| Digit DP | O(log N) | O(log N * 10) | O(log N * 10 * StateSize) | O(log N) (Recursion Depth) |
Continue the DSA curriculum
Dynamic Programming is one of 12 topics in the interactive DSA visualizer curriculum. Once this topic is comfortable, the coding interview pattern library reorganises the same material around the patterns interview questions are built on.
Every other DSA visualizer
Data Structures · 28 lessons
- StackFree
- QueueFree
- Deque
- Circular Queue
- Priority Queue (ADT)
- Tree Traversal
- Binary Tree
- Binary Search Tree
- AVL Tree
- Trie (Prefix Tree)
- Segment Tree
- Fenwick Tree
- Red-Black Tree
- Singly Linked List
- Doubly Linked List
- Circular Linked List
- Graph RepresentationFree
- Breadth First SearchFree
- Depth First Search
- Topological Sort
- Cycle Detection
- Connected Components
- Bipartite Graph
- Dijkstra's Algorithm
- Bellman-Ford Algorithm
- Minimum Spanning Tree
- Floyd-Warshall Algorithm
- Bridges & Articulation Points