Memoisasi vs Tabulasi
Dua cara untuk menyimpan jawaban subsoal
Memoisasi vs Tabulasi adalah pelajaran Competitive Programming Academy gratis di CoddyKit. Ini adalah pelajaran 1 dari 4. Kamu bisa membaca pelajaran lengkapnya di bawah secara gratis — lalu praktikkan langsung di browser dengan editor kode bawaan dan tutor AI 24/7. Ini adalah bagian dari jalur belajar Competitive Programming Academy, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus Competitive Programming Academy mencakup 4 pelajaran total.
Mengapa Menyimpan Hasil
Rekursi naif mengulangi pekerjaan yang sama berkali-kali. Pemrograman dinamis menyimpan setiap jawaban sekali sehingga Anda tidak perlu menghitungnya kembali.
fib(40) # slow: recomputes endlesslySubmasalah yang Tumpang Tindih
DP berlaku ketika sebuah masalah terbagi menjadi submasalah yang tumpang tindih. Kasus kecil yang sama muncul di banyak cabang rekursi.
fib(5) needs fib(3) twiceDari Atas ke Bawah: Memoisasi
Memoisasi adalah rekursi biasa yang ditambah penyimpanan hasil. Anda menghitung sesuai kebutuhan dan mengingat hasilnya saat pertama kali melihat setiap masukan.
memo = {}Memoisasi Mudah di Python
Dekorator lru_cache mengubah rekursi lambat menjadi DP cepat dalam satu baris, dengan menyimpan setiap pemanggilan secara otomatis.
from functools import lru_cache
@lru_cache(None)
def f(n): ...Dari Bawah ke Atas: Tabulasi
Tabulasi mengisi tabel mulai dari kasus terkecil hingga jawaban, menggunakan perulangan sebagai pengganti rekursi.
dp = [0] * (n + 1)Fibonacci dengan Tabulasi
Atur nilai dasar, lalu biarkan setiap sel membaca nilai yang sudah dihitung. Tidak ada tumpukan pemanggilan, hanya perulangan yang rapi.
dp[0], dp[1] = 0, 1
for i in range(2, n+1):
dp[i] = dp[i-1] + dp[i-2]Hasil Sama, Gaya Berbeda
Memoisasi dan tabulasi menyelesaikan rekurensi yang sama. Perbedaannya hanya pada arah: dari atas ke bawah sesuai kebutuhan, atau dari bawah ke atas secara berurutan.
Kapan Memilih Memoisasi
Pilih memoisasi ketika rekurensinya alami untuk ditulis dan Anda mungkin tidak memerlukan setiap keadaan.
Kapan Memilih Tabulasi
Pilih tabulasi untuk perulangan yang ketat, untuk menghindari kesalahan batas rekursi, dan ketika Anda memang akan menghitung seluruh tabel.
import sys; sys.setrecursionlimit(10**6)Perhatikan Batas Rekursi
Rekursi bermemoisasi yang dalam dapat mencapai batas rekursi Python dan berhenti dengan hasil kesalahan saat berjalan pada masukan berukuran besar.
Keduanya Memiliki Satu Biaya
Apa pun pendekatannya, peningkatan kecepatan berasal dari menyelesaikan setiap keadaan sekali. Waktu total adalah jumlah keadaan dikali pekerjaan untuk setiap keadaan.
Pemeriksaan Singkat
Pendekatan mana yang mengisi tabel dari bawah ke atas menggunakan perulangan?
Rekapitulasi: Dua Cara, Satu DP
Sekarang Anda dapat menyimpan submasalah dengan dua cara. Memoisasi melakukan rekursi dari atas ke bawah, sedangkan tabulasi melakukan perulangan dari bawah ke atas. Pilih cara yang paling mudah dibaca. ✨
Pertanyaan yang Sering Diajukan
Apakah pelajaran “Memoisasi vs Tabulasi” gratis?
Ya — teks lengkap “Memoisasi vs Tabulasi” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus Competitive Programming Academy, upgrade ke CoddyKit PRO. Kursus Competitive Programming Academy mencakup 4 pelajaran total.
Apa yang akan aku pelajari di “Memoisasi vs Tabulasi”?
Dua cara untuk menyimpan jawaban subsoal Kamu berlatih Competitive Programming Academy dengan kode praktik yang langsung kamu jalankan di browser, dan tutor AI 24/7 menjawab pertanyaanmu saat kamu mengerjakan pelajaran ini.
Apakah aku perlu pengalaman untuk memulai Competitive Programming Academy?
Tidak diperlukan pengalaman sebelumnya. Competitive Programming Academy di CoddyKit dirancang untuk pemula hingga pelajar tingkat lanjut, jadi kamu bisa memulai di sini atau dari awal dan belajar sesuai kecepatan kamu sendiri. Ini adalah pelajaran 1 dari 4.
Berapa lama pelajaran “Memoisasi vs Tabulasi” memakan waktu?
Sebagian besar pelajaran CoddyKit memakan waktu sekitar 5–10 menit. Setiap pelajaran ringkas dan interaktif, jadi kamu membuat kemajuan stabil dan melanjutkan dari tempat kamu tinggalkan di web dan aplikasi.
Bisakah aku menulis dan menjalankan kode dalam pelajaran Competitive Programming Academy ini?
Ya. Setiap pelajaran Competitive Programming Academy menyertakan editor kode bawaan, jadi kamu menulis dan menjalankan kode nyata langsung di browser dan mendapatkan umpan balik AI instan — tidak diperlukan penyiapan lokal.
Semua pelajaran dalam kursus ini
- Memoisasi vs Tabulasi
- Mendefinisikan State dan Transisi
- Menaiki Tangga & Kombinasi Koin
- Subsekuens Naik Terpanjang