Dynamic Programming problems, grouped by pattern
Dynamic programming is recursion that remembers. Start from the recursive choice, add memoisation, then turn it into a table. The patterns move from 1D and grid DP to stock state machines, knapsack, string alignment and interval DP.
When to reach for it
- Count the ways, or find the min or max over choices
- Overlapping subproblems in the recursion tree
- Two strings compared character by character
Mistakes to watch for
- Wrong base cases for empty input
- Iterating capacity in the wrong direction for 0/1 knapsack
- Defining dp[i] without writing down what it means
The 34 problems
11D DP
- Fibonacci Number Animated Easy
- Climbing Stairs Animated Easy
- Min Cost Climbing Stairs (2 jumps) Animated Easy
- Minimal Cost (k jumps) Animated Medium
- Decode Ways Animated Medium
- Word Break Animated Medium
2Alternate Selection / Pick / Not pick
- House Robber Animated Medium
- House Robber II Animated Medium
32D DP
- Minimum Path Sum Animated Medium
- Unique Paths Animated Medium
- Unique Paths II Animated Medium
42D DP - max/min of last row
- Minimum Falling Path Sum Animated Medium
- Triangle Animated Medium
- Geek's Training Animated Medium
5Squares
- Maximal Square Animated Medium
- Count Square Submatrices with All Ones Animated Medium
- Largest 1-Bordered Square Animated Medium
6State Machine DP - Stock Problems
- Best Time to Buy and Sell Stock Animated Easy
- Best Time to Buy and Sell Stock II Animated Medium
- Best Time to Buy and Sell Stock with Transaction Fee Animated Medium
- Best Time to Buy and Sell Stock with Cooldown Animated Medium
- Best Time to Buy and Sell Stock III Animated Hard
7Knapsack
- 0 - 1 Knapsack Problem Animated Medium
- Fractional Knapsack Animated Medium
- Knapsack with Duplicate Items Animated Medium
- Coin Change Animated Medium
- Coin Change II Animated Medium
8Strings
- Edit Distance Animated Medium
- Longest Common Subsequence Animated Medium
- Longest Palindromic Subsequence Animated Medium
- Minimum Insertion Steps to Make a String Palindrome Animated Hard
- Longest Common Substring Animated Medium
9Interval DP
- Matrix Chain Multiplication Animated Hard
- Burst Balloons Animated Hard