Menghitung Jalur pada Grid

Anda mulai dari kiri atas sebuah kisi dan ingin mencapai kanan bawah. Setiap langkah bergerak ke kanan atau ke bawah. Berapa banyak jalur berbeda yang ada?

Setiap sel dapat dicapai dari sel di atasnya atau sel di sebelah kirinya. Tumpang tindih itulah alasan tepat mengapa ini merupakan masalah DP.

Misalkan dp[i][j] adalah banyaknya cara untuk mencapai sel (i, j) dari titik awal. Menamai keadaan dengan jelas berarti Anda sudah menyelesaikan separuh tantangan.

Anda hanya dapat tiba dari atas atau dari kiri, sehingga jumlahnya adalah penjumlahan keduanya. Inilah transisi yang menggerakkan seluruh tabel.

Sel awal memiliki tepat satu cara untuk mencapainya: tidak melakukan apa pun. Jadi, dp[0][0] bernilai 1 sebelum Anda mengisi bagian lainnya.

Sel pada baris teratas atau kolom paling kiri hanya memiliki satu rute lurus. Jumlahnya selalu 1 karena salah satu tetangganya berada di luar kisi.

Buat tabel m kali n yang diisi dengan nol. Menentukan ukurannya sejak awal membuat pengindeksan tetap rapi dan menghindari kejutan.

Lakukan perulangan pada baris, lalu kolom, dari atas ke bawah dan dari kiri ke kanan. Urutan ini menjamin kedua tetangga sudah siap sebelum digunakan.

Setelah pengisian selesai, jumlah jalur berada di sel terakhir. Jawabannya adalah dp[m-1][n-1], yaitu sudut kanan bawah.

Setiap baris hanya membutuhkan baris di atasnya, sehingga Anda dapat menyimpan satu baris dan memperbaruinya di tempat. Dengan begitu, memori berkurang menjadi O(n).

Tanpa penghalang, jawabannya adalah koefisien binomial: pilih langkah mana dari seluruh langkah yang bergerak ke bawah. DP tetap lebih unggul ketika rintangan muncul.

Tentukan dp sebagai jalur menuju sebuah sel, atur dp[0][0] menjadi 1, lalu jumlahkan sel di atas dan sel di kiri. Sudut kisi menyimpan jawaban Anda. 🧭