Dynamic Programming: Define State Before Storage

Write a sentence for every state

House Robber allows selecting nothing: best[0] = 0 and best[1] = nums[0] for a nonempty input. That does not mean every DP starts at zero. Minimum-coin DP initializes unreachable positive amounts to Infinity; only amount zero needs zero coins.

Derive skip-or-take choices before compressing storage

Let best[i] be the maximum total from the first i houses. Skip house i-1 to keep best[i-1], or take it and add nums[i-1] to best[i-2]. Thus best[i] = max(best[i-1], best[i-2] + nums[i-1]). Taking a house excludes its immediate neighbor, not every earlier house.

Before processing index i, oneBack stores best[i] and twoBack stores best[max(0, i-1)]. Compute current before replacing either value. After the update, oneBack stores best[i+1]. The loop also handles an empty array by returning zero.

function rob(nums) {
  let twoBack = 0, oneBack = 0;
  for (const amount of nums) {
    const current = Math.max(oneBack, twoBack + amount);
    twoBack = oneBack;
    oneBack = current;
  }
  return oneBack;
}

• Updating twoBack before computing current would read the wrong prefix and can allow adjacent houses. Save the new answer first, then shift the two prior answers.
• Two stored totals are enough to return the optimum, but do not identify the chosen houses. Keep the prefix table and backtrack through skip-or-take decisions when reconstruction is required; ties can have several valid optimal selections.

Trace the two choices for each house

For [2,7,9,3,1], the full prefix table is [0,2,7,11,11,12]. Taking indices 0, 2, and 4 yields 12. A greedy rule that always takes the largest next house misses that 2 + 9 beats 7. Choosing one index parity globally is also insufficient: [2,1,1,2] is best solved by taking the two endpoints for 4.

Choose dependency order and scope

• Memoization discovers needed states recursively; tabulation orders dependencies explicitly. Both still require the same complete state key.
• House Robber II splits the cycle into two linear cases: exclude the first or exclude the last. The one-house case must not accidentally become two empty ranges.
• Tree DP has its own guide: conditional subtree return values are not a one-dimensional prefix recurrence.
• Some DP problems admit stronger algorithms. LIS has an O(N squared) predecessor DP and an O(N log N) tails method; do not assume a table is always the final optimization.

Count states times transition work

• House Robber costs O(N) time: each prefix has two constant-time choices. The full table uses O(N) auxiliary space; the displayed code uses O(1).
• Other DP problems can cost more per state. For Word Break, trying several earlier split points and checking their words adds work beyond counting prefix positions.
• Memoization recursion adds call-stack storage and may hit JavaScript depth limits. Output reconstruction, slicing, and dictionary checks add costs beyond the nominal DP state count.

Mistakes and Counterexamples