Demo önizleme: Bu çözümler otomatik test paketini geçiyor ama insan tarafından incelenmedi. Trade-off ve yazıları taslak olarak değerlendirin.

Mediumone-dimensional-dp

House Robber

Problem (restated)

Rob houses in a line; cannot rob adjacent houses. Maximize total money.

Intuition

At each house: rob it (+ skip previous) or skip it (take previous best).

Approaches

1D DP

Tested only

Time O(n)Space O(1)

Idea. dp[i] = max(dp[i-1], dp[i-2] + nums[i]); roll two vars.

Walkthrough. [2,7,9,3,1] → 2+9+1=12 or 7+3+… best 12.

Trade-offs. O(1) space after realizing only last two states matter.

Solution

export function rob(nums: number[]): number {
  let prev2 = 0, prev1 = 0;
  for (const x of nums) {
    const cur = Math.max(prev1, prev2 + x);
    prev2 = prev1;
    prev1 = cur;
  }
  return prev1;
}

export function rob(nums: number[]): number {
  let prev2 = 0, prev1 = 0;
  for (const x of nums) {
    const cur = Math.max(prev1, prev2 + x);
    prev2 = prev1;
    prev1 = cur;
  }
  return prev1;
}

Template connection

One-dimensional DP choose/skip.

Reflection

Which pattern gave this away within 90 seconds?
What changed from the standard template?
What would break the current solution?