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

Bir sıradaki evleri soy; komşu evleri soyamazsın. Toplam parayı maksimize et.

Sezgi

Her evde: onu soy (+ öncekini atla) veya atla (önceki en iyiyi al).

Yaklaşımlar

1B DP

Doğrulanmadı

Zaman O(n)Alan O(1)

Fikir. dp[i] = max(dp[i-1], dp[i-2] + nums[i]); iki değişken kaydır.

Yürüyüş. [2,7,9,3,1] → 2+9+1=12 veya 7+3+… en iyi 12.

Trade-off. Yalnızca son iki durumun önemli olduğunu fark edince O(1) alan.

Çözüm

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

Şablon bağlantısı

Tek boyutlu DP seç/atla.

Yansıma

dp[i] = max(dp[i-1], dp[i-2] + nums[i]). Komşu ev yok. Atlamak dp[i-1].
Tek ev o ev. İlk iki ev: ikisinin büyüğü. Hepsi 0 ise 0.
İki değişken yeter. Sağdan sola aynı cevap, komşuluk değişmez.