Pengiraan Laluan pada Grid
Jumlahkan laluan dari satu penjuru ke penjuru yang lain.
Pengiraan Laluan pada Grid ialah pelajaran Persediaan Temu Duga Pengaturcaraan percuma di CoddyKit. Ini ialah pelajaran 1 daripada 4. Anda boleh membaca keseluruhan pelajaran di bawah secara percuma — kemudian berlatih secara praktikal dalam pelayar menggunakan penyunting kod terbina dalam dan tutor kecerdasan buatan 24/7. Pelajaran ini merupakan sebahagian daripada laluan pembelajaran Persediaan Temu Duga Pengaturcaraan, dan kemajuan anda disegerakkan merentas web serta aplikasi CoddyKit. Kursus Persediaan Temu Duga Pengaturcaraan merangkumi sejumlah 4 pelajaran.
Masalah Klasik Berpetak
Anda bermula di penjuru kiri atas sebuah jadual petak dan mahu sampai ke penjuru kanan bawah. Setiap langkah bergerak ke kanan atau ke bawah. Berapakah bilangan laluan berbeza yang wujud?
Mengapa DP Sesuai
Setiap sel boleh dicapai dari sel di atas atau sel di sebelah kirinya. Pertindihan itu tepat sebab masalah ini sesuai diselesaikan dengan DP.
Tentukan Keadaan
Biarkan dp[i][j] menjadi bilangan cara untuk mencapai sel (i, j) dari permulaan. Menamakan keadaan dengan jelas ialah separuh daripada usaha menyelesaikan masalah.
Peralihan
Anda hanya boleh tiba dari atas atau dari kiri, jadi bilangannya ialah jumlah kedua-duanya. Inilah peralihan yang menggerakkan seluruh jadual.
dp[i][j] = dp[i-1][j] + dp[i][j-1]Kes Asas
Sel permulaan mempunyai tepat satu cara untuk dicapai: tidak melakukan apa-apa. Jadi dp[0][0] ialah 1 sebelum anda mengisi sel lain.
dp[0][0] = 1Tepi Mempunyai Satu Laluan
Sel di baris paling atas atau lajur paling kiri mempunyai satu laluan lurus. Bilangannya sentiasa 1 kerana salah satu jirannya berada di luar jadual.
Bina Jadual
Bina jadual m darab n yang diisi dengan sifar. Menetapkan saiznya dari awal memastikan pengindeksan anda kemas dan mengelakkan kejutan.
dp = [[0] * n for _ in range(m)]Isi Mengikut Susunan Bacaan
Ulang baris kemudian lajur, dari atas ke bawah dan dari kiri ke kanan. Susunan ini memastikan kedua-dua jiran telah sedia sebelum anda menggunakannya.
for i in range(m):
for j in range(n):
...Sel Jawapan
Selepas pengisian selesai, bilangan laluan berada dalam sel terakhir. Jawapannya ialah dp[m-1][n-1], iaitu penjuru kanan bawah.
answer = dp[m-1][n-1]Jimat Memori dengan Satu Baris
Setiap baris hanya memerlukan baris di atasnya, jadi anda boleh menyimpan satu baris dan mengemas kininya di tempat yang sama. Ini mengurangkan memori kepada O(n).
row[j] += row[j-1]Pintasan Matematik
Tanpa halangan, jawapannya ialah pekali binomial: pilih langkah yang bergerak ke bawah daripada jumlah keseluruhan langkah. DP tetap lebih berkesan apabila halangan muncul.
Semakan Pantas
Anda sedang mengisi dp[i][j] untuk sel dalaman yang terbuka. Rumus manakah yang betul?
Imbas Kembali: Pengiraan Laluan
Tentukan dp sebagai laluan ke sesuatu sel, tetapkan dp[0][0] kepada 1, kemudian tambah sel di atas dengan sel di kiri. Penjuru itu menyimpan jawapan anda. 🧭
Pelajari Persediaan Temu Duga Pengaturcaraan dengan tutor kecerdasan buatan — percuma
Tulis dan jalankan kod sebenar dalam pelayar anda, dapatkan bantuan segera daripada tutor kecerdasan buatan yang tersedia 24/7, dan sambung semula dari tempat anda berhenti di web atau dalam aplikasi.
- Kursus
- 90
- Pelajaran
- 360
Soalan Lazim
Adakah pelajaran “Pengiraan Laluan pada Grid” percuma?
Ya — teks penuh “Pengiraan Laluan pada Grid” boleh dibaca secara percuma di web ini. Untuk berlatih secara interaktif menggunakan penyunting kod terbina dalam dan tutor kecerdasan buatan 24/7, serta membuka kunci baki kursus Persediaan Temu Duga Pengaturcaraan, tingkat taraf kepada CoddyKit PRO. Kursus Persediaan Temu Duga Pengaturcaraan merangkumi sejumlah 4 pelajaran.
Apakah yang akan saya pelajari dalam “Pengiraan Laluan pada Grid”?
Jumlahkan laluan dari satu penjuru ke penjuru yang lain. Anda berlatih Persediaan Temu Duga Pengaturcaraan menggunakan kod praktikal yang dijalankan terus dalam pelayar, manakala tutor kecerdasan buatan 24/7 menjawab soalan anda semasa anda mengikuti pelajaran.
Adakah saya memerlukan pengalaman untuk memulakan Persediaan Temu Duga Pengaturcaraan?
Tiada pengalaman terdahulu diperlukan. Pembelajaran Persediaan Temu Duga Pengaturcaraan di CoddyKit disusun untuk pelajar daripada peringkat pemula hingga lanjutan, jadi anda boleh bermula di sini atau dari awal dan belajar mengikut kadar anda sendiri. Ini ialah pelajaran 1 daripada 4.
Berapa lamakah pelajaran “Pengiraan Laluan pada Grid” diambil?
Kebanyakan pelajaran CoddyKit mengambil masa kira-kira 5–10 minit. Setiap pelajaran ringkas dan interaktif, jadi anda boleh membuat kemajuan secara berterusan dan menyambung tepat dari tempat anda berhenti di web atau aplikasi.
Bolehkah saya menulis dan menjalankan kod dalam pelajaran Persediaan Temu Duga Pengaturcaraan ini?
Ya. Setiap pelajaran Persediaan Temu Duga Pengaturcaraan menyertakan penyunting kod terbina dalam, jadi anda boleh menulis dan menjalankan kod sebenar terus dalam pelayar serta menerima maklum balas kecerdasan buatan serta-merta — tanpa memerlukan persediaan setempat.
Semua pelajaran dalam kursus ini
- Pengiraan Laluan pada Grid
- Jumlah Laluan Minimum dengan Halangan
- Subjujukan Sepunya Terpanjang
- Jarak Suntingan Langkah demi Langkah