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

Problem (yeniden ifade)

m×n ızgaranın sol üstündeki robot yalnızca sağa veya aşağı gidebilir. Sağ alta kaç yol vardır?

Sezgi

dp[r][c] = üstten + soldan; kenarlar 1.

Yaklaşımlar

2B DP

Doğrulanmadı

Zaman O(m*n)Alan O(n)

Fikir. Tek satır kaydır; dp[c] += dp[c-1].

Adım adım. m=3,n=7 → 28.

Ödünleşimler. Kombinasyon C(m+n-2,m-1) de çalışır.

Çözüm

export function uniquePaths(m: number, n: number): number {
  const dp = new Array<number>(n).fill(1);
  for (let r = 1; r < m; r++) {
    for (let c = 1; c < n; c++) dp[c] = dp[c]! + dp[c - 1]!;
  }
  return dp[n - 1]!;
}

export function uniquePaths(m: number, n: number): number {
  const dp = new Array<number>(n).fill(1);
  for (let r = 1; r < m; r++) {
    for (let c = 1; c < n; c++) dp[c] = dp[c]! + dp[c - 1]!;
  }
  return dp[n - 1]!;
}

Şablon bağlantısı

İki boyutlu DP ızgarası.

Yansıma

Yalnızca sağ ve aşağı. dp[r][c] = üst + sol. İlk satır ve ilk sütun 1.
m = 1 veya n = 1: tek yol, cevap 1. Engel yok.
Hücre (0,0) 1. Büyük ızgarada ara toplam taşmasın.