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

Minimum Path Sum

Problem (yeniden ifade)

Negatif olmayan m×n ızgara. Sol üstten sağ alta yol (yalnızca sağ/aşağı). Toplamı minimize et.

Sezgi

dp[i][j] = grid + min(üstten, soldan). Önce ilk satır/sütun, sonra kalanı doldur.

Yaklaşımlar

Yerinde ızgara DP

Tested only

Time O(mn)Space O(1) extra

Fikir. Izgarayı değiştirebilirsin: grid[i][j] += min(up, left).

Adım adım. [[1,3,1],[1,5,1],[4,2,1]] → 7 (1→3→1→1→1).

Ödünleşimler. Unique paths ailesinin aynısı; maliyet eklenir.

Solution

export function minPathSum(grid: number[][]): number {
  const m = grid.length, n = grid[0]!.length;
  for (let i = 1; i < m; i++) grid[i]![0]! += grid[i - 1]![0]!;
  for (let j = 1; j < n; j++) grid[0]![j]! += grid[0]![j - 1]!;
  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      grid[i]![j]! += Math.min(grid[i - 1]![j]!, grid[i]![j - 1]!);
    }
  }
  return grid[m - 1]![n - 1]!;
}

export function minPathSum(grid: number[][]): number {
  const m = grid.length, n = grid[0]!.length;
  for (let i = 1; i < m; i++) grid[i]![0]! += grid[i - 1]![0]!;
  for (let j = 1; j < n; j++) grid[0]![j]! += grid[0]![j - 1]!;
  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      grid[i]![j]! += Math.min(grid[i - 1]![j]!, grid[i]![j - 1]!);
    }
  }
  return grid[m - 1]![n - 1]!;
}

Şablon bağlantısı

İki boyutlu DP ızgara durumları.

Yansıma

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