Recap — From Memoization to Tabulation

# From Memoization to Tabulation DP is the most-feared interview topic. It's also one of the most pattern-based — most DP problems fit a handful of templates. ## The DP recipe 1. **Identify the state.** What inputs determine the subproblem? Usually one or two parameters. 2. **Define the recurrence.** How does dp[state] relate to smaller states? 3. **Identify base cases.** Where does the recursion bottom out? 4. **Choose top-down or bottom-up.** ## Approach 1: Top-down (memoization) Recursion + cache. Solve recursively, store results. ```python from functools import lru_cache @lru_cache(maxsize=None) def fib(n): if n <= 1: return n return fib(n - 1) + fib(n - 2) ``` `@lru_cache` is the Python shortcut. Manually: ```python def fib(n, memo={}): if n in memo: return memo[n] if n <= 1: return n memo[n] = fib(n - 1, memo) + fib(n - 2, memo) return memo[n] ``` Pros: closely follows the recursive thinking; only computes states you need. Cons: recursion overhead; stack depth can be a problem. ## Approach 2: Bottom-up (tabulation) Iterative, build a table from base cases up. ```python def fib(n): if n <= 1: return n dp = [0] * (n + 1) dp[1] = 1 for i in range(2, n + 1): dp[i] = dp[i-1] + dp[i-2] return dp[n] ``` Often more space-efficient (can drop old rows). No recursion overhead. ```python # Even smaller: O(1) space def fib(n): if n <= 1: return n a, b = 0, 1 for _ in range(n): a, b = b, a + b return a ``` Choose top-down for clarity; bottom-up for performance and clean state handling. ## Classic 1D DP problems ### Climbing stairs (Fibonacci-like) "You can take 1 or 2 steps. How many ways to climb N stairs?" ```python def climb_stairs(n): if n <= 2: return n dp = [0] * (n + 1) dp[1], dp[2] = 1, 2 for i in range(3, n + 1): dp[i] = dp[i-1] + dp[i-2] return dp[n] ``` Recurrence: dp[i] = dp[i-1] + dp[i-2]. State = number of stairs left. ### House robber "Rob houses in a row; can't rob adjacent. Maximize loot." ```python def rob(nums): if not nums: return 0 prev1, prev2 = 0, 0 for n in nums: prev1, prev2 = max(prev2 + n, prev1), prev1 return prev1 ``` Recurrence: dp[i] = max(dp[i-1], dp[i-2] + nums[i]). "Skip current or rob it." ### Maximum subarray sum (Kadane's algorithm) "Find contiguous subarray with maximum sum." ```python def max_subarray(nums): best = current = nums[0] for x in nums[1:]: current = max(x, current + x) # extend or restart best = max(best, current) return best ``` Recurrence: at each i, either start fresh or extend the previous best. ### Coin change (minimum coins) "Minimum coins to make amount." ```python def coin_change(coins, amount): dp = [float('inf')] * (amount + 1) dp[0] = 0 for i in range(1, amount + 1): for c in coins: if c <= i: dp[i] = min(dp[i], dp[i - c] + 1) return dp[amount] if dp[amount] != float('inf') else -1 ``` Recurrence: dp[i] = min over coins c of dp[i-c] + 1. State = amount remaining. ## Classic 2D DP problems ### Longest common subsequence (LCS) ```python def lcs(s1, s2): m, n = len(s1), len(s2) dp = [[0] * (n + 1) for _ in range(m + 1)] for i in range(1, m + 1): for j in range(1, n + 1): if s1[i-1] == s2[j-1]: dp[i][j] = dp[i-1][j-1] + 1 else: dp[i][j] = max(dp[i-1][j], dp[i][j-1]) return dp[m][n] ``` State: (i, j) = lengths of prefixes considered. Recurrence: match or pick best of skipping one. ### 0/1 Knapsack "N items with weight and value; max value with weight limit W." ```python def knapsack(weights, values, W): n = len(weights) dp = [[0] * (W + 1) for _ in range(n + 1)] for i in range(1, n + 1): for w in range(W + 1): dp[i][w] = dp[i-1][w] # skip item if weights[i-1] <= w: dp[i][w] = max(dp[i][w], dp[i-1][w - weights[i-1]] + values[i-1]) return dp[n][W] ``` State: (i, w) = first i items, capacity w. Recurrence: take or skip. ### Edit distance "Min operations (insert/delete/replace) to transform s1 to s2." ```python def edit_distance(s1, s2): m, n = len(s1), len(s2) dp = [[0] * (n + 1) for _ in range(m + 1)] for i in range(m + 1): dp[i][0] = i for j in range(n + 1): dp[0][j] = j for i in range(1, m + 1): for j in range(1, n + 1): if s1[i-1] == s2[j-1]: dp[i][j] = dp[i-1][j-1] else: dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) return dp[m][n] ``` Three operations correspond to three predecessors. ## The DP pattern catalog | Pattern | State | Examples | |---|---|---| | Linear (1D) | dp[i] | Fib, climb stairs, house robber, coin change | | Two-pointer (2D) | dp[i][j] | LCS, edit distance, longest palindrome substring | | Knapsack (2D) | dp[i][weight] | 0/1, unbounded, partition