Dynamic Programming Language
Memoization, tabulation, recurrence relations, subproblems, and space optimization vocabulary
Dynamic programming vocabulary
- Memoization — top-down; cache recursive results; compute lazily
- Tabulation — bottom-up; fill table iteratively from smallest subproblems
- Recurrence — dp[i] = f(dp[i-1], ...); read: "how each state depends on previous states"
- Base case — the smallest known value(s) the recurrence starts from
- Space optimization — if dp[i] only needs dp[i-1], use two variables instead of an array
Question 0 of 5
A code review comment says: "This solution uses memoization to avoid recomputing subproblems." What does memoization mean?
Caching function results so the same inputs are never computed twice. Memoization vocabulary:
- Memoization — top-down DP; add a cache to a recursive function; compute lazily on demand
- Cache / memo table — typically a dict/Map:
memo[args] = result - Cache hit — the result is already in the cache; return immediately (O(1))
- Cache miss — compute the result, store it, then return
How is "tabulation" different from "memoization" in dynamic programming?
Tabulation = bottom-up (iterative, fills table from base); memoization = top-down (recursive, caches on demand). Comparing DP approaches:
- Tabulation (bottom-up): start from the smallest subproblems, fill the table in order; no recursion overhead; typically O(N) space with a 1D or 2D array
- Memoization (top-down): start from the original problem, recurse, cache; natural from the recursive definition; may not compute all subproblems
dp[0]=0, dp[1]=1, dp[2]=1, ... iteratively. Memoization wraps fib(n) with a cache check. Both produce the same answer in O(N) time, but tabulation has no call stack overhead.A function docstring says: "Solves this by breaking it into overlapping subproblems and combining their solutions." What programming technique does this describe?
Dynamic programming — overlapping subproblems solved once and reused. Algorithm paradigm vocabulary:
- Dynamic programming — optimal substructure + overlapping subproblems; reuse cached results
- Divide and conquer — split into independent (non-overlapping) subproblems; merge results; e.g., merge sort, binary search
- Greedy — always take the locally best option; works only when local optimum → global optimum (e.g., Dijkstra's, Huffman coding)
- Backtracking — explore all options, undo (backtrack) when a dead end is reached; e.g., N-Queens, Sudoku solver
In a design doc: "We define the DP recurrence as dp[i] = dp[i-1] + dp[i-2], with base cases dp[0] = 0 and dp[1] = 1." What problem does this solve?
Fibonacci sequence — each term is the sum of the two preceding terms. DP recurrence vocabulary:
- Recurrence relation — the formula expressing a solution in terms of smaller subproblems:
dp[i] = dp[i-1] + dp[i-2] - Base cases — the smallest subproblems with known answers:
dp[0] = 0, dp[1] = 1 - State — what dp[i] represents; here: "the i-th Fibonacci number"
A colleague says: "We can optimize this DP solution's space from O(N) to O(1) because each step only looks at the previous two values." What technique are they describing?
Space optimization: keep only the states needed, not the entire table. DP space optimization vocabulary:
- Standard Fibonacci DP:
dp = [0] * (n+1)→ O(N) space - Optimized:
prev2, prev1 = 0, 1; update in-place → O(1) space - This works whenever each step only needs a fixed number of previous states (not all of them)
dp[i] only depends on dp[i-1] and dp[i-2], keep only two variables. If it depends on the entire row above in a 2D table, keep only one row (O(N) instead of O(N²)). Code review phrase: "dp[i] only uses dp[i-1] — we can replace the array with two variables and reduce space from O(N) to O(1)."