Dynamic Programming Flashcards
What are the two main techniques used in Dynamic Programming?
Memoization (Top-Down), Tabulation (Bottom-Up).
What is the difference between top-down (memoization) and bottom-up (tabulation) DP?
Memoization uses recursion + caching, Tabulation uses loops.
What is the time complexity of solving Fibonacci with DP?
O(n).
How does the Knapsack problem use DP?
Optimize item selection within weight constraints.
What is the difference between DP and Greedy algorithms?
DP finds global optimal, Greedy finds local optimal.
What are key signals that a problem can be solved using Dynamic Programming?
Overlapping Subproblems → Solving the same subproblems repeatedly
Optimal Substructure → The solution is built from smaller solutions
Decision Making → Choosing between different ways to solve subproblems
what is top down good for
Solves only necessary subproblems, faster for sparse problems
what is bottom up good for
✅ Iterative, no recursion overhead, good for full-table problems
What are the three places you need to identify in a dp problem?
Key Insight
Base Case
Recurrence Relation
What are the steps to breaking down a dp problem
- Identify Overlapping Subproblems
If a problem breaks into smaller versions of itself, DP is a good fit.
- Find a Recurrence Relation
Whether bottom-up or top-down, DP is all about finding how the solution for dp[i][j] depends on dp[i+1][j-1] or dp[i+1][j].
- Decide Between Recursion (Top-Down) or Iteration (Bottom-Up)
Top-Down: Naturally follows from recursion, helpful in deriving the formula.
Bottom-Up: Helps see dependencies clearly in the DP table.
Go through an example of identifying dp formulas using Longest Palindromic Subsequence problem
- key insight is if s[i] === s[j] then theres a substring because you can remove letters in between
2.
What question should you ask to recognize dp problems?
Can the solution be expressed in terms of solutions to similar smaller problems?
Whats a good question to ask when trying to understand input params dp?
Which inputs/parameters decrease as the problem size reduces
what is recurrence formula for fibonacci
🟢 1. Fibonacci-Type (Simple Recurrence)
Pattern: Solve dp[i] using dp[i-1] and dp[i-2].
✅ Example: Fibonacci numbers, Climbing Stairs, Tribonacci.
🔹 Formula:
dp[i] = dp[i-1] + dp[i-2]
Base: dp[0]=0, dp[1]=1
what is recurrence formula for knapsack
🔵 2. Knapsack-Type (Subset Selection)
Pattern: Decide whether to include an element or not (binary choice).
✅ Example: 0/1 Knapsack, Subset Sum, Partition Equal Subset Sum.
🔹 Formula:
dp[i][w] = max(dp[i-1][w], val[i] + dp[i-1][w-weight[i]])
Base: dp[0][] = 0 (no items), dp[][0] = 0 (zero capacity)
What about for unbouned knapsack
🟠 3. Unbounded Knapsack-Type (Infinite Choices)
Pattern: Similar to knapsack but items can be reused.
✅ Example: Coin Change (min coins), Rod Cutting, Integer Break.
🔹 Formula:
dp[i] = min(dp[i - coin] + 1 for coin in coins)
Base: dp[0] = 0
What is recurrence formala for longest subsequence?
🟣 4. Longest Subsequence-Type
Pattern: Compare characters/elements, build solutions iteratively.
✅ Example: Longest Common Subsequence (LCS), Longest Palindromic Subsequence.
🔹 Formula:
If s[i] === s[j]: dp[i][j] = 2 + dp[i+1][j-1]
Else: dp[i][j] = max(dp[i+1][j], dp[i][j-1])
What is recurrence formula for partition problems
🟤 6. Partition DP (Splitting Problems)
Pattern: Partition the problem into segments and solve subproblems.
✅ Example: Matrix Chain Multiplication, Burst Balloons, Palindrome Partitioning.
🔹 Formula:
dp[i][j] = min(dp[i][k] + dp[k+1][j] + cost(i,k,j))
What is recurrence formula for game theory?
🟢 8. Game Theory DP
Pattern: Player strategies with optimal choices.
✅ Example: Predict the Winner, Stone Game, Nim Game.
🔹 Formula:
dp[i][j] = max(arr[i] - dp[i+1][j], arr[j] - dp[i][j-1])
