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 81 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
- Maximum Profit in Job Scheduling Hard
- Longest Increasing Subsequence Medium
- Delete and Earn Medium
- Race Car Hard
- Concatenated Words Hard
- Paint House Medium
- Longest String Chain Medium
- Russian Doll Envelopes Hard
- Frog Jump Hard
- Unique Binary Search Trees Medium
- Maximum Earnings From Taxi Medium
- Minimum Cost For Tickets Medium
- Pascal's Triangle II Easy
- Pascal's Triangle Easy
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
- Dungeon Game Hard
- Number of Dice Rolls With Target Sum Medium
- Super Egg Drop Hard
- Cherry Pickup Hard
- Find the N-th Value After K Seconds Medium
- Maximum Amount of Money Robot Can Earn Medium
- Minimum Cost to Reach Destination in Time Hard
- Maximum Number of Events That Can Be Attended II Hard
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
- Partition Equal Subset Sum Medium
- Number of Ways to Build House of Cards Medium
- Target Sum Medium
- Painting the Walls Hard
- Split Array With Same Average Hard
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
- Longest Palindromic Substring Medium
- Longest Valid Parentheses Hard
- Regular Expression Matching Hard
- Distinct Subsequences Hard
- Palindrome Partitioning II Hard
- Maximum Length of Repeated Subarray Medium
- Number of Ways to Form a Target String Given a Dictionary Hard
- Palindromic Substrings Medium
- Wildcard Matching Hard
- Number of Ways to Separate Numbers Hard
9Interval DP
- Matrix Chain Multiplication Animated Hard
- Burst Balloons Animated Hard
- Predict the Winner Medium
- The Score of Students Solving Math Expression Hard
- Strange Printer Hard