Dynamic Programming
Master dynamic programming — identify overlapping subproblems, build optimal solutions from sub-solutions, and solve classic DP problems.
55 min•By Priygop Team•Last updated: Feb 2026
DP Fundamentals
- When to Use DP: Problem has overlapping subproblems (same subproblem solved multiple times) AND optimal substructure (optimal solution contains optimal solutions to subproblems)
- Top-Down (Memoization): Start from the main problem, recurse into subproblems, cache results. Natural recursive thinking. Use when subproblem space is sparse
- Bottom-Up (Tabulation): Build solution from smallest subproblems up. Iterative, fills a table. Usually faster (no recursion overhead). Use when all subproblems needed
- State Definition: The hardest part — define what dp[i] or dp[i][j] represents. Example: dp[i] = longest increasing subsequence ending at index i
- Transition: How to compute dp[i] from previously computed values. Example: dp[i] = max(dp[j] + 1) for all j < i where arr[j] < arr[i]
- Space Optimization: If dp[i] depends only on dp[i-1], use two variables instead of an array. Reduces O(n) space to O(1). Common in Fibonacci, coin change
Classic DP Problems
- Fibonacci: dp[i] = dp[i-1] + dp[i-2]. Base: dp[0]=0, dp[1]=1. Space-optimized with two variables. The 'Hello World' of DP
- Longest Common Subsequence (LCS): dp[i][j] = length of LCS of first i chars and first j chars. If match: dp[i-1][j-1]+1. Else: max(dp[i-1][j], dp[i][j-1])
- 0/1 Knapsack: dp[i][w] = max value using first i items with capacity w. Either include item i (value[i] + dp[i-1][w-weight[i]]) or exclude (dp[i-1][w])
- Longest Increasing Subsequence (LIS): dp[i] = length of LIS ending at index i. For each j < i where arr[j] < arr[i]: dp[i] = max(dp[i], dp[j]+1). O(n²), or O(n log n) with binary search
- Edit Distance: dp[i][j] = min operations to convert first i chars to first j chars. Operations: insert, delete, replace. Used in spell checkers, DNA sequencing
- Coin Change: dp[amount] = minimum coins to make that amount. For each coin: dp[i] = min(dp[i], dp[i-coin]+1). Bottom-up from 0 to target amount