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

Mediumtwo-dimensional-dp

Unique Paths II

Problem (yeniden ifade)

Engelli (1) bir ızgarada robot sol üstten sağ alta (yalnızca sağ/aşağı). Yolları say; tamamen engellenirse 0.

Sezgi

Unique Paths ile aynı, ancak engel hücresinin 0 yolu vardır ve yayılmaz.

Yaklaşımlar

Engelleri sıfırlayan 1B DP

Doğrulanmadı

Zaman O(mn)Alan O(n)

Fikir. Kaydıran satır dp[c]: engelse 0; değilse dp[c] += dp[c-1] (sol). Üst/sol engeller sıfırlarla yansır.

Adım adım. [[0,0,0],[0,1,0],[0,0,0]] → ortadaki engelin etrafından 2 yol.

Ödünleşimler. Temiz 0 dönüşü için başlangıç/bitiş engellerini erken kontrol et.

Çözüm

export function uniquePathsWithObstacles(obstacleGrid: number[][]): number {
  const m = obstacleGrid.length;
  const n = obstacleGrid[0]!.length;
  if (obstacleGrid[0]![0] === 1 || obstacleGrid[m - 1]![n - 1] === 1) return 0;
  const dp = Array(n).fill(0);
  dp[0] = 1;
  for (let r = 0; r < m; r++) {
    for (let c = 0; c < n; c++) {
      if (obstacleGrid[r]![c] === 1) {
        dp[c] = 0;
      } else if (c > 0) {
        dp[c] += dp[c - 1]!;
      }
    }
  }
  return dp[n - 1]!;
}

export function uniquePathsWithObstacles(obstacleGrid: number[][]): number {
  const m = obstacleGrid.length;
  const n = obstacleGrid[0]!.length;
  if (obstacleGrid[0]![0] === 1 || obstacleGrid[m - 1]![n - 1] === 1) return 0;
  const dp = Array(n).fill(0);
  dp[0] = 1;
  for (let r = 0; r < m; r++) {
    for (let c = 0; c < n; c++) {
      if (obstacleGrid[r]![c] === 1) {
        dp[c] = 0;
      } else if (c > 0) {
        dp[c] += dp[c - 1]!;
      }
    }
  }
  return dp[n - 1]!;
}

Şablon bağlantısı

Engelli hücrelerle ızgara yol DP’si.

Yansıma

1D satır. Engel hücreyi 0 yapar. Değilse sol artı üst. İlk engelden sonra ilk satır 0 kalır.
Başlangıç engelse cevap 0. Engel yoksa LC62 ile aynı.
Tek boş hücre 1. Tek engel hücre 0.