Dynamic Programming
State design, knapsack, string DP, LIS and state machines.
11 notes · 49 min total
Questions0 of 65 done
Warm up with these before Phase 1.
Patterns
- 1DP Overview & State DesignHow to spot a DP problem, name its pattern from the wording, and design a state whose cache key captures everything.7 min
- 21-D Linear DP: House Robber FamilySolve take-or-skip problems along a line, where taking one position blocks its neighbor, and reduce new problems to House Robber.4 min
- 31-D DP: Min/Max to Reach a TargetFind the fewest pieces (or best product, or any split) that build an exact target, with a 1-D state on the amount left.4 min
- 40/1 Knapsack: Take or SkipDecide take-or-skip for each item once, and recognize subset sum, equal partition and min-difference partition in disguise.4 min
- 5Unbounded Knapsack: Combinations vs PermutationsCount the ways to build a target from reusable pieces, and control whether order matters with the state or the loop order.4 min
- 6Grid & Path DPCount or optimize paths through a grid, including move budgets, probabilities and walks on a small graph.5 min
- 7Two-String DPCompare two strings with a dp[i][j] state on their indices: LCS, edit distance, interleaving and pattern matching.4 min
- 8Palindrome & Interval DPSolve range problems with dp over (i, j): shrink palindromes from both ends, and split ranges by choosing the last action.4 min
- 9LIS FamilyFind the longest increasing subsequence in O(n²) and O(n log n), count how many there are, and handle 2-D nesting.5 min
- 10State-Machine DPModel problems as a few named states (hold, sold, rest) with transitions per step, as in the stock buy/sell series.5 min
- 11Game / Minimax DPSolve two-player optimal-play games by returning the score difference for whoever moves next.3 min