� Complete DP + Recursion Decision Notes
Interview-Ready Cheat Sheet
Step-0: First Thing to Check
Before coding, ask yourself:
1. Are we exploring choices?
2. Do subproblems repeat?
3. How big is the state space (n × W )?
� Golden Identification Rule
PRINT ALL → Recursion/Backtracking | BEST VALUE → DP | COUNT WAYS → DP
� Quick Decision Table
Situation Approach
Generate all subsets/permutations Recursion
Tree/Graph traversal Recursion
Optimal Answer (Max/Min) DP
Count Ways DP
Overlapping States DP
n small (< 20) Recursion is fine
n large DP required
W large (1D DP possible) DP (Space Optimized)
State huge Greedy / Math
When SIMPLE RECURSION is Enough
Use recursion only when n ≤ 20 − 25, no overlapping subproblems exist, or you need to generate
every possible result.
• Examples: Subsets, Permutations, N-Queens, DFS, Backtracking.
function solve(i, path) {
if (i === n) {
[Link] ([... path ]); // Only if we need to store ALL results
return ;
}
[Link](arr[i]); // Choose
solve(i + 1, path);
[Link] (); // Un - choose ( Backtrack )
solve(i + 1, path);
}
1
When Recursion Fails (TLE) → Use DP
If you notice overlapping subproblems (e.g., solve(3, 10) being called multiple times), you must
use DP.
• Recurrence Rule: State must only contain changing variables that matter for future decisions.
• Good State: (index, remainingWeight)
• Bad State: (index, fullArrayPath) → Too large to memoize.
� Constraint → Approach Formula
Estimate states: Total States = n × W .
• ≤ 107 : Safe for DP.
• ≥ 108 : Risky, needs 1D optimization or Greedy.
2
� 0/1 Knapsack Templates
1. Memoization (Top-Down)
let dp = [Link] ({ length : n }, () => Array(W + 1).fill (-1));
function solve(i, w) {
if (i === n || w === 0) return 0;
if (dp[i][w] !== -1) return dp[i][w];
let take = 0;
if (wt[i] <= w) take = val[i] + solve(i + 1, w - wt[i]);
let notTake = solve(i + 1, w);
return dp[i][w] = [Link](take , notTake );
}
2. Tabulation (Bottom-Up)
let dp = [Link] ({ length : n + 1 }, () => Array(W + 1).fill (0));
for (let i = 1; i <= n; i++) {
for (let w = 0; w <= W; w++) {
if (wt[i -1] <= w) {
dp[i][w] = [Link](val[i -1] + dp[i -1][w - wt[i -1]] , dp[i -1][w]);
} else {
dp[i][w] = dp[i -1][w];
}
}
}
return dp[n][W];
3. Space Optimized (1D)
let dp = Array(W + 1).fill (0);
for (let i = 0; i < n; i++) {
for (let w = W; w >= wt[i]; w--) { // Backward for 0/1, Forward for Unbounded
dp[w] = [Link](dp[w], val[i] + dp[w - wt[i]]);
}
}
� Interview Script
When an interviewer presents a problem, follow this verbal path:
1. ”I’ll start with a recursive approach to understand the choices and base cases.”
2. ”I notice overlapping subproblems here, so I will add a memoization table to reduce time complexity.”
3. ”To optimize for space and avoid recursion stack limits, I’ll convert this to a bottom-up tabulation
approach.”
4. ”Finally, I can optimize the space to 1D if we only need the previous row’s data.”
3
� Final Cheat Rule
• 0/1 Knapsack: Inner loop goes backward (W → 0).
• Unbounded Knapsack: Inner loop goes forward (0 → W ).
• Memory Check: JS Safe limit is ≈ 107 array elements.