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

Tested only

Time O(mn)Space 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.

Solution

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

Bu problemi 90 saniye içinde hangi kalıp ele verdi?
Standart şablondan ne değişti?
Mevcut çözümü ne bozar?