Ones and Zeroes

Problem (yeniden ifade)

İkili dizgiler strs; m sıfır ve n bir bütçesi. Bütçeleri aşmadan oluşturulabilecek en büyük dizgi alt kümesi.

Sezgi

Her dizgi maliyeti (sıfır, bir) ve değeri 1 olan bir eşya. Klasik 0/1 knapsack, 2D kapasite.

Yaklaşımlar

export function findMaxForm(strs: string[], m: number, n: number): number {
  const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));
  for (const s of strs) {
    let zeros = 0, ones = 0;
    for (const c of s) if (c === "0") zeros++; else ones++;
    for (let i = m; i >= zeros; i--) {
      for (let j = n; j >= ones; j--) {
        dp[i]![j] = Math.max(dp[i]![j]!, dp[i - zeros]![j - ones]! + 1);
      }
    }
  }
  return dp[m]![n]!;
}

export function findMaxForm(strs: string[], m: number, n: number): number {
  const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));
  for (const s of strs) {
    let zeros = 0, ones = 0;
    for (const c of s) if (c === "0") zeros++; else ones++;
    for (let i = m; i >= zeros; i--) {
      for (let j = n; j >= ones; j--) {
        dp[i]![j] = Math.max(dp[i]![j]!, dp[i - zeros]![j - ones]! + 1);
      }
    }
  }
  return dp[m]![n]!;
}

Şablon bağlantısı

Çok boyutlu kapasiteli 0/1 knapsack.

Yansıma

• Her dizgi bir kez. m ve n döngüleri geriye. dp[z][o] o bütçeyle en çok dizgi.
• İleri döngü aynı dizgiyi tekrar sayar. 0 ve 1 sayısı bütçeyi aşan dizgi atlanır.
• m = n = 0: boş dizgi varsa 1. Boş liste 0.