Dynamic Programming
Break a problem into overlapping subproblems. Memoize results (top-down) or fill a table bottom-up. Works when the problem has optimal substructure.
Time
O(n²) or O(n·m) typically
Space
O(n) to O(n·m)
Recognize it when
- Count ways / find min/max ways to reach a goal
- Optimal substructure: solution built from subproblem solutions
- "How many ways...?" or "What is the minimum cost...?"
- Substring/subsequence problems (LCS, LIS)
Questions — ordered by difficulty
Climbing Stairs
Count the number of ways to climb n stairs, taking 1 or 2 steps at a time.
House Robber
Rob houses to maximize money without robbing two adjacent houses.
Partition Equal Subset Sum
Determine if an array can be partitioned into two subsets with equal sum.
Coin Change
Find the minimum number of coins needed to make up a given amount.
Longest Common Subsequence
Find the length of the longest subsequence common to two strings.
Word Break
Determine if a string can be segmented into words from a dictionary.
Unique Paths
Count unique paths from top-left to bottom-right of an m×n grid (only right or down moves).
Edit Distance
Find the minimum number of operations (insert, delete, replace) to convert word1 to word2.
Maximum Subarray
Find the contiguous subarray with the largest sum (Kadane's algorithm).
Burst Balloons
Burst balloons to maximize coins. Bursting balloon i gives nums[i-1]*nums[i]*nums[i+1] coins.
Maximum Product Subarray
Find the contiguous subarray with the largest product. The array may contain negative numbers and zeros.
Jump Game
Given an array where nums[i] is the maximum jump length from position i, determine if you can reach the last index.
Distinct Subsequences
Count the number of distinct subsequences of string s that equal string t.
Jump Game II
Find the minimum number of jumps to reach the last index (you are guaranteed to reach it).
Wildcard Matching
Implement wildcard pattern matching with '?' (any single character) and '*' (any sequence including empty).
Decode Ways
A string of digits can be decoded as letters (1→A, 2→B, ..., 26→Z). Count the number of ways to decode it.
Interleaving String
Check if s3 is formed by interleaving s1 and s2 while preserving their relative order.
Longest Increasing Subsequence
Find the length of the longest strictly increasing subsequence.
Longest Palindromic Substring
Find the longest substring of s that is a palindrome.
Palindromic Substrings
Count how many substrings of s are palindromes.
Russian Doll Envelopes
Find the maximum number of envelopes you can nest (each must be strictly larger in both dimensions).
Regular Expression Matching
Implement regex matching with '.' (matches any single character) and '*' (matches zero or more of the preceding element).
Coin Change II
Count the number of combinations of coins that make up the amount (unlimited coins of each denomination).
Target Sum
Assign + or - to each number to reach a target sum. Count the number of ways.