Master Dynamic Programming with 30 Flashcards: Memoization, Knapsack, LCS and Bitmask DP
Master dynamic programming with deck AI3432: 30 flashcards on memoization, tabulation, knapsack, LCS, LIS, edit distance, Kadane, bitmask and digit DP.
Studying. But it's also a video game. 🎮
Flashcards, quizzes and games that make you actually remember.
Posted by
FLIP IT TeamRelated reading
Study Guide: Software Testing in 40 Flashcards — Unit, Integration and 30 More Test Types
Learn software testing with 40 flashcards: unit vs integration, the test pyramid, smoke vs sanity, load vs stress, code coverage, mutation testing and TDD.
Learn Big O Notation in German: 44 Flashcards on Landau-Notation, Schranken and Sorting Costs
German edition of the Big O flashcard deck: obere, untere and scharfe Schranke, Mergesort, Knoten and Kanten, plus three cards to fix before you study.
Learn Big O Notation in Spanish: 44 Flashcards on Notación Big O
Study Big O notation in Spanish with 44 flashcards: cota superior, inferior y ajustada, tiempo linearítmico, peor caso, plus three cards to fix first.
Dynamic programming is where most interview prep stalls: the problems look different, but they all run on the same machinery. Deck AI3432 "Dynamic Programming" fits that machinery into 30 tight cards. Each one is a definition, a classic problem or an advanced technique, with its complexity attached.
Study this deck: Dynamic Programming
1 / 10Dynamic programming
Tap the card for the answer · swipe right if you knew it, left if not
Ten cards that carry the deck
| Front | Back |
|---|---|
| Two key properties needed for DP | Optimal substructure + overlapping subproblems |
| Memoization (top-down DP) | Recursively solve, storing results in a cache; lazy evaluation |
| Tabulation (bottom-up DP) | Iteratively solve subproblems from base cases; avoids recursion overhead |
| Fibonacci as a DP problem | Naive recursion O(2ⁿ) → DP O(n) time, O(1) space |
| Recurrence for 0/1 Knapsack | dp[i][w] = max(dp[i-1][w], dp[i-1][w-wᵢ] + vᵢ) |
| LCS recurrence | If X[i]==Y[j]: 1 + dp[i-1][j-1]; else max(dp[i-1][j], dp[i][j-1]) |
| Kadane's maximum subarray | dp[i] = max(nums[i], dp[i-1] + nums[i]), O(n) |
| Partition Equal Subset Sum | Reduces to subset sum with target = total_sum/2 |
| TSP DP solution | O(2ⁿ × n²) bitmask DP; dp[mask][i] = min cost ending at city i |
| DP vs greedy | Greedy picks local optima; DP considers all subproblems and guarantees the global optimum |
The full problem list
You'll cover Fibonacci, Climbing Stairs, 0/1 and unbounded knapsack, Rod Cutting, Coin Change (min coins and number of ways), Subset Sum, Partition Equal Subset Sum, House Robber (line and circle), Kadane's algorithm, LCS, LIS (O(n²) and O(n log n) with binary search), Edit Distance (Levenshtein), Palindrome Partitioning, Matrix Chain Multiplication (O(n³)) and TSP. It also covers four techniques: space optimization (O(n²) → O(n)), DP on trees (diameter, max independent set), digit DP with tight-bound tracking, and bitmask DP.
How to study it
Group the problems by family, not by deck order. Linear 1D DP covers Climbing Stairs, House Robber and Kadane. Two-string 2D DP covers LCS, Edit Distance and Palindrome Partitioning. Capacity DP covers the knapsack family: 0/1 knapsack, unbounded knapsack, Rod Cutting, Coin Change and Subset Sum. Interval DP is Matrix Chain, and subset DP is TSP. Once you know the family, you can usually rebuild the state.
Write the missing recurrence cards. Only six cards give an actual formula: Fibonacci, knapsack, LCS, Kadane, Climbing Stairs and TSP. Edit Distance, Coin Change, LIS, House Robber, Subset Sum and Rod Cutting only give the problem and its complexity. Interviews test the transition, so add one card per problem whose back is the recurrence. For example, Edit Distance: dp[i][j] = dp[i-1][j-1] if the characters match, else 1 + min(insert, delete, substitute). For unbounded knapsack, add the one-index change: dp[i][w-wᵢ] instead of dp[i-1][w-wᵢ].
To place DP's O(nW) and O(2ⁿ × n²) costs among the other complexity classes, pair this deck with our Big O notation guide and the sorting, searching and graph algorithms deck.
Ready to learn faster? 🚀
Join FLIP IT for free and turn studying into a game.