Overlapping subproblems, memoization versus tabulation, knapsack, LCS, edit distance, coin change and DP on grids and intervals.
40 cards · basic cards · AI-written, checked twice. Edit anything.
- What is dynamic programming?
Show answer
An algorithmic technique that solves optimization problems by breaking them into overlapping subproblems, storing solutions to avoid redundant computation.- Define overlapping subproblems in DP.
Show answer
A problem exhibits overlapping subproblems when the same subproblems are solved multiple times in a naive recursive approach.- Define optimal substructure.
Show answer
A problem has optimal substructure if an optimal solution can be constructed from optimal solutions to its subproblems.- What is memoization?
Show answer
A top-down DP approach that uses recursion and stores results of subproblems to avoid recomputation.- How does memoization work algorithmically?
Show answer
Call the recursive function, check if the result is cached before computing, cache the result, and return it.- What is tabulation?
Show answer
A bottom-up DP approach that builds a table iteratively starting from base cases and computing larger subproblems using smaller ones.- How does tabulation work algorithmically?
Show answer
Initialize a table with base cases, then iteratively fill the table using a recurrence relation until reaching the final answer.- Memoization vs tabulation: which uses less auxiliary space in typical problems?
Show answer
Tabulation often uses less space because it overwrites old values, while memoization must keep the entire recursion call stack.- Memoization vs tabulation: which is typically easier to implement?
Show answer
Memoization is easier because you write the recursive logic directly and add caching, while tabulation requires careful loop ordering.- When is memoization preferable to tabulation?
Show answer
When you only need to compute a subset of subproblems, or when the problem state space is sparse or hard to iterate in order.- When is tabulation preferable to memoization?
Show answer
When you must solve all subproblems, want to avoid call stack overhead, or need guaranteed iteration order and control.- Define the 0/1 Knapsack problem.
Show answer
Given a knapsack of capacity W and n items with weights and values, select items to maximize value without exceeding capacity, using each item at most once.- What are the base cases for 0/1 Knapsack DP?
Show answer
If capacity is 0 or there are no items remaining, the maximum value is 0.- What is the recurrence relation for 0/1 Knapsack?
Show answer
dp[i][w] = max(dp[i-1][w], dp[i-1][w-weight[i]] + value[i]) if weight[i] <= w, else dp[i-1][w].- What is the time complexity of 0/1 Knapsack?
Show answer
O(n*W) where n is the number of items and W is the knapsack capacity.
FlashKeepers