The 4-Step Framework to Solve Any Dynamic Programming Problem in Technical Interviews

When an interviewer gives you a DP problem, jumping straight into a 2D table usually causes brain-freeze. Use this 4-step framework out loud:

1. Step 1: Identify State & Parameters: Ask yourself: "What variables change as I make decisions?" (e.g. current index i, remaining capacity w). Those variables define your DP state: dp(i, w).
2. Step 2: Write the Pure Recursion & Recurrence Relation: Formulate the choices:
   • Choice A: Exclude current item dp(i + 1, w)
   • Choice B: Include current item val[i] + dp(i + 1, w - wt[i]) (if wt[i] <= w)
   • Return max(Choice A, Choice B)
3. Step 3: Add Memoization (Top-Down): Cache the result in a table or hash map before returning. This drops time complexity from $O(2^N)$ to $O(N \times W)$.
4. Step 4: Bottom-Up & Space Optimization (Bonus): If the interviewer asks to optimize memory, observe that dp[i] only depends on dp[i-1], allowing you to reduce $O(N \times W)$ space to a single $O(W)$ 1D array.

Interviewers award 80% of marks for explaining Step 1 and Step 2 cleanly.