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 II

Problem (restated)

Houses in a circle (first adjacent to last). Cannot rob adjacent houses. Maximize money.

Intuition

Cannot take both ends. Answer = max(rob [0..n-2], rob [1..n-1]) with classic linear House Robber DP.

Approaches

Two linear robber ranges

Tested only

Time O(n)Space O(1)

Idea. Handle n=1 specially. Reuse O(1) rolling DP on each open range.

Walkthrough. [2,3,2] → 3; [1,2,3,1] → 4.

Trade-offs. Circle breaks pure linear recurrence; case split fixes it.

Solution

export function rob(nums: number[]): number {
  const n = nums.length;
  if (n === 1) return nums[0]!;
  const linear = (l: number, r: number): number => {
    let prev2 = 0, prev1 = 0;
    for (let i = l; i <= r; i++) {
      const cur = Math.max(prev1, prev2 + nums[i]!);
      prev2 = prev1;
      prev1 = cur;
    }
    return prev1;
  };
  return Math.max(linear(0, n - 2), linear(1, n - 1));
}

export function rob(nums: number[]): number {
  const n = nums.length;
  if (n === 1) return nums[0]!;
  const linear = (l: number, r: number): number => {
    let prev2 = 0, prev1 = 0;
    for (let i = l; i <= r; i++) {
      const cur = Math.max(prev1, prev2 + nums[i]!);
      prev2 = prev1;
      prev1 = cur;
    }
    return prev1;
  };
  return Math.max(linear(0, n - 2), linear(1, n - 1));
}

Template connection

1D House Robber with circular constraint.

Reflection

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