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

Tested only

Time O(m*n)Space 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.

Solution

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

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