Maximal Square

Problem (yeniden ifade)

‘0’/‘1’ ikili matrisi. Yalnızca 1 içeren en büyük karenin alanını döndür.

Sezgi

dp[i][j] = (i-1,j-1)’de biten max kare kenarı. Hücre 1 ise: 1+min(üst, sol, çapraz).

Yaklaşımlar

export function maximalSquare(matrix: string[][]): number {
  const m = matrix.length;
  const n = matrix[0]!.length;
  const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));
  let best = 0;
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (matrix[i - 1]![j - 1] === "1") {
        dp[i]![j] =
          1 + Math.min(dp[i - 1]![j]!, dp[i]![j - 1]!, dp[i - 1]![j - 1]!);
        best = Math.max(best, dp[i]![j]!);
      }
    }
  }
  return best * best;
}

export function maximalSquare(matrix: string[][]): number {
  const m = matrix.length;
  const n = matrix[0]!.length;
  const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));
  let best = 0;
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (matrix[i - 1]![j - 1] === "1") {
        dp[i]![j] =
          1 + Math.min(dp[i - 1]![j]!, dp[i]![j - 1]!, dp[i - 1]![j - 1]!);
        best = Math.max(best, dp[i]![j]!);
      }
    }
  }
  return best * best;
}

Şablon bağlantısı

Durumu yol sayısı değil geometrik boyut olan ızgara DP.

Yansıma

• Hücre 1 ise kenar min(sol, üst, çapraz) + 1, değilse 0. Cevap en büyük kenarın karesi.
• Yalnızca üç komşu kareyi büyütür. Tek 1 alan 1. Hepsi 0 alan 0.
• Tam 1 dolu ızgarada kenar min(m, n). 2×2 içinde tek 0 kenarı 1’de tutar.