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 (yeniden ifade)

Evler çember (ilki sonuncuya bitişik). Bitişik evler soyulamaz. Parayı maksimize et.

Sezgi

Her iki ucu birden alamazsın. Cevap = max(soy [0..n-2], soy [1..n-1]) klasik doğrusal House Robber DP ile.

Yaklaşımlar

İki doğrusal soygun aralığı

Doğrulanmadı

Zaman O(n)Alan O(1)

Fikir. n=1’i özel işle. Her açık aralıkta O(1) kaydırmalı DP’yi yeniden kullan.

Yürüyüş. [2,3,2] → 3; [1,2,3,1] → 4.

Trade-off. Çember saf doğrusal yinelemeyi bozar; durum ayrımı düzeltir.

Çözüm

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));
}

Şablon bağlantısı

Dairesel kısıtlı 1B House Robber.

Yansıma

İlk ve son ev komşu. İki doğrusal soygun: ilki hariç ve sonuncusu hariç. Cevap ikisinin büyüğü.
n = 1 o ev. n = 2 ikisinin büyüğü. İkisini birden soymak çemberi bozar.
Aralık fonksiyonu LC198. Boş aralık 0.