DP has a scary reputation, but it is one idea: solve each subproblem once, remember the answer. Needed for TCS Digital/Prime and every product company.
The idea in 6 lines
// fib without DP: O(2ⁿ) — recomputes everything
// fib with tabulation: O(n)
function fib(n) {
const dp = [0, 1];
for (let i = 2; i <= n; i++) dp[i] = dp[i-1] + dp[i-2];
return dp[n];
}The 3-problem on-ramp
- 1. Climbing Stairs: ways(n) = ways(n-1) + ways(n-2). Literally fibonacci. Solve it
- 2. House Robber: at each house: rob it (+ dp[i-2]) or skip (dp[i-1]). Take max
- 3. Coin Change: dp[amount] = min coins; for each amount try every coin. Solve it
How to recognize DP
- The question asks for max/min/count of ways
- Choices at each step affect later options
- Brute force would recompute the same states
Memoization vs tabulation
Memoization = recursion + cache (top-down, easier to write). Tabulation = fill an array bottom-up (faster, no stack limits). Learn memo first, convert to table when needed.
← All Articles