İki Boyutlu DP

Nasıl düşünülür

dp[i][j] = i ve j öneki (veya hücre (i,j)) alt probleminin cevabı. Artan i+j veya satır tarayarak doldur. Cevap genelde dp[m][n] veya dp[m-1][n-1]’de.

Şablon şekilleri

Şekil	Temel hamle	Notlar
Izgara yolları	üst/soldan	Engeller sıfırlar
String DP	eşleşme → diag+1	yoksa skip min/max
Yuvarlanan dizi	Yalnızca önceki satır	Alan tasarrufu

Karmaşıklık temeli

O(m·n) zaman ve alan (veya yuvarlanan ile O(min(m,n)) alan).

Şablondan probleme

1. dp[i][j]’yi kelimelerle tanımla.
2. İlk satır/sütunu başlat.
3. Yinelemenin geometrik komşularından geçiş.
4. Köşe hücreyi döndür.

/** 2D DP template: unique paths (right/down only). dp[c] rolled per row. */
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]!;
}

/** 2D DP template: unique paths (right/down only). dp[c] rolled per row. */
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]!;
}