Handling a DP question under pressure

DP questions punish silence, because the thinking is invisible until the recurrence appears. Work out loud, in this order.

1. Solve a tiny case by hand

n = 3, on paper, saying each step. This surfaces the choice structure faster than staring at the general case, and it gives you test data for later.

2. Write the brute force recursion

Even if it is exponential. It is correct, it names the state, and it is worth partial credit on its own.

// "At index i with capacity c, either take this item or skip it."
const best = (i, c) =>
  i =<mark> items.length || c </mark>= 0
    ? 0
    : Math.max(
        best(i + 1, c),
        items[i].weight <= c ? items[i].value + best(i + 1, c - items[i].weight) : 0,
      );

3. Say the complexity, then point at the overlap

"This is O(2ⁿ) because each item branches twice — but (i, c) repeats across branches, and there are only n × capacity distinct pairs."

That sentence is the DP insight. Say it before you write the memo.

4. Add memoisation

Mechanical once the state is named. Now quote the new complexity: states × work per state.

5. Offer tabulation and space reduction

"Bottom-up removes the recursion; and since each row only reads the row above, one array is enough — O(capacity) space." Offer it; implement it if there is time.

6. Test the edges

Empty input, single element, everything identical, the target unreachable. Walk your n = 3 example through the finished code out loud.

What loses points

• Jumping straight to a table you cannot justify. If asked why dp[i][j] means what you claim and you cannot answer, the whole solution reads as memorised.
• Silence while thinking. Narrate the choice structure even when you are stuck: "each step I either take this or skip it, so the state must include where I am and what I have left."
• Ignoring the constraints. n ≤ 20 says bitmask or backtracking; n ≤ 10⁵ says a DP with O(n) or O(n log n), not O(n²).

The honest fallback

If the recurrence will not come, say so and deliver the memoised brute force with its complexity, plus the direction you would take next. A correct exponential solution with a clear analysis beats a broken table, and it leaves the door open for a hint you can actually use.