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

Mediumknapsack-subset-dp

Last Stone Weight II

Problem (yeniden ifade)

İki taşı a,b çarpıştır: a≠b ise |a-b| ağırlığında bir taş kalır. Son taşın ağırlığını minimize et (yoksa 0).

Sezgi

Taşları toplamları mümkün olduğunca eşit iki yığına bölmeye eşdeğer; cevap, sum/2’ye en yakın alt küme toplamı S için |sum-2S|.

Yaklaşımlar

Yarıya en yakın bölme

Doğrulanmadı

Zaman O(n·Σ)Alan O(Σ)

Fikir. target=sum/2 için boolean alt küme toplamı DP; en büyük ulaşılabilir s’yi al; sum-2s döndür.

Adım adım. [2,7,4,1,8,1] → 1.

Trade-off’lar. Partition Equal Subset Sum ile aynı çekirdek; eşitliği kontrol etmek yerine farkı minimize et.

Çözüm

export function lastStoneWeightII(stones: number[]): number {
  const total = stones.reduce((a, b) => a + b, 0);
  const target = Math.floor(total / 2);
  const dp = Array(target + 1).fill(false);
  dp[0] = true;
  for (const x of stones) {
    for (let c = target; c >= x; c--) dp[c] = dp[c] || dp[c - x];
  }
  for (let s = target; s >= 0; s--) if (dp[s]) return total - 2 * s;
  return total;
}

export function lastStoneWeightII(stones: number[]): number {
  const total = stones.reduce((a, b) => a + b, 0);
  const target = Math.floor(total / 2);
  const dp = Array(target + 1).fill(false);
  dp[0] = true;
  for (const x of stones) {
    for (let c = target; c >= x; c--) dp[c] = dp[c] || dp[c - x];
  }
  for (let s = target; s >= 0; s--) if (dp[s]) return total - 2 * s;
  return total;
}

Şablon bağlantısı

Alt küme toplamı / bölme DP.

Yansıma

İki yığının farkı, toplamın yarısına en yakın alt kümenin artığı. Cevap sum - 2*closest.
0/1 geriye döngü. Tek taş kendisi. İki eşit taş 0.
Bu yok etme sırası değil, iki grubun ağırlık farkı.