Memoization: Menyimpan Hasil Rekursif

Fibonacci rekursif naif menghitung nilai yang sama berulang kali. fib(5) memanggil fib(4) dan fib(3); fib(4) memanggil fib(3) dan fib(2)—jadi fib(3) dihitung dua kali. Redundansi ini berkembang secara eksponensial: fib(40) melakukan lebih dari satu miliar pemanggilan fungsi. Memoisasi mengatasi hal ini dengan menyimpan setiap hasil saat pertama kali dihitung, sehingga pemanggilan berikutnya mengambilnya dalam O(1), bukan menghitungnya ulang.

Tambahkan kamus memo sebagai parameter (atau penutupan). Sebelum menghitung, periksa apakah jawabannya sudah ada dalam kamus. Jika ya, segera kembalikan. Jika tidak, hitung, simpan dalam kamus, lalu kembalikan. Setiap submasalah unik kini dihitung tepat satu kali, sehingga O(2^n) berubah menjadi waktu O(n) dan ruang O(n) untuk kamus memoisasi, ditambah ruang tumpukan O(n).

Python menyediakan @functools.lru_cache(maxsize=None) (juga tersedia sebagai @functools.cache di Python 3.9+) untuk mengotomatiskan memoisasi. Menambahkan dekorator ini di atas sebuah fungsi menyimpan semua pemanggilan berdasarkan argumennya. maxsize=None berarti ukuran tembolok tak terbatas—setiap kombinasi argumen unik disimpan dalam tembolok. Hal ini mengubah fungsi rekursif apa pun menjadi versi yang dimemoisasi hanya dengan satu baris kode.

LeetCode 70 'Mendaki Tangga': Anda dapat menaiki 1 atau 2 anak tangga sekaligus. Ada berapa cara untuk mencapai anak tangga ke-n? Ini pada dasarnya adalah Fibonacci: ways(n) = ways(n-1) + ways(n-2). Kasus dasar: ways(0) = 1 (satu cara untuk tetap berada di lantai dasar), ways(1) = 1. Dengan memoisasi, waktunya O(n) dan ruangnya O(n).

LeetCode 322 'Penukaran Koin': diberikan nilai pecahan koin dan jumlah target, tentukan jumlah minimum koin. Rekursi dimemoisasi dari atas ke bawah: dp(amount) = 1 + min(dp(amount - coin)) untuk setiap koin yang valid. Kasus dasarnya: dp(0) = 0. Simpan setiap subjumlah dalam tembolok. Jika suatu subjumlah tidak mungkin dicapai, kembalikan tak terhingga. Memoisasi mengubah pendekatan coba-coba eksponensial menjadi waktu O(jumlah × panjang(daftar koin)).

LeetCode 139 'Pemisahan Kata': tentukan apakah sebuah untai dapat dipisahkan menjadi kata-kata dalam kamus. Rekursi dari atas ke bawah: can_break(s, start) mencoba setiap awalan s[start:end]; jika awalan tersebut ada di dalam kamus dan can_break(s, end) bernilai benar, kembalikan benar. Tanpa memoisasi, kompleksitasnya O(2^n); dengan memoisasi (menyimpan setiap indeks awal), kompleksitasnya menjadi O(n² × L), dengan L sebagai panjang kata maksimum.

Memoisasi (dari atas ke bawah) dimulai dari masalah awal dan menyimpan jawaban saat submasalah ditemukan secara rekursif. Pendekatan ini hanya menyelesaikan submasalah yang benar-benar diperlukan. Tabulasi (dari bawah ke atas) terlebih dahulu mengisi tabel dari submasalah kecil ke besar, sehingga semua submasalah diselesaikan tanpa memandang kebutuhannya. Memoisasi lebih mudah diturunkan dari solusi rekursif; tabulasi menghindari keterbatasan kedalaman rekursi dan beban pemanggilan fungsi.

Banyak masalah DP yang dapat diselesaikan oleh rekursi yang dimemoisasi dalam ruang O(n) dapat lebih dioptimalkan menjadi ruang O(1) ketika hanya diperlukan sejumlah tetap jawaban submasalah sebelumnya. Untuk Fibonacci, hanya dua nilai terakhir yang penting. Untuk mendaki tangga, prinsipnya sama. Menggulirkan dua variabel menggantikan seluruh kamus memoisasi atau tabel.

Ada tiga cara untuk menerapkan memoisasi secara manual. Kamus global sederhana, tetapi mengotori cakupan modul. Penutupan membungkus tembolok di dalam fungsi, sehingga mencegah kebocoran, tetapi memerlukan pembungkus. @lru_cache adalah pilihan yang paling rapi—satu dekorator menggantikan semua kode pendukung. Dalam konteks wawancara, mulailah dengan @lru_cache kecuali pewawancara secara khusus meminta implementasi manual.

Memoisasi hanya mempercepat masalah dengan submasalah yang tumpang tindih—kasus ketika submasalah yang sama dihitung beberapa kali. Jika setiap submasalah unik (seperti dalam penelusuran pohon sederhana ketika setiap simpul dikunjungi tepat satu kali), memoisasi menambah beban tanpa manfaat. Selain itu, memoisasi tidak dapat memperbaiki masalah ketika pohon rekursif bersifat eksponensial dalam jumlah submasalah yang berbeda, bukan karena penggunaan ulang—masalah seperti itu memerlukan algoritma yang sama sekali berbeda.

Terapkan memoisasi ketika: Anda memiliki solusi rekursif yang benar tetapi lambat karena perhitungan ulang yang berlebihan, fungsi memiliki sejumlah kecil kombinasi argumen yang berbeda, dan nilai kembalian hanya bergantung pada argumen (fungsi murni—tanpa efek samping dan tanpa keadaan global). Periksa ruang keadaan submasalah: jika terdapat paling banyak O(n) atau O(n²) keadaan yang berbeda, memoisasi mengubah waktu eksponensial menjadi waktu polinomial.

Dalam pelajaran ini Anda mempelajari: memoisasi menyimpan hasil submasalah untuk menghindari perhitungan ulang, sehingga mengubah rekursi eksponensial menjadi waktu polinomial, @functools.lru_cache adalah alat Python idiomatis yang hanya memerlukan satu baris, dan memoisasi (dari atas ke bawah) serta tabulasi (dari bawah ke atas) adalah dua gaya DP—memoisasi lebih mudah diturunkan, sedangkan tabulasi menghindari masalah kedalaman tumpukan. Selamat—Anda telah menyelesaikan modul rekursi dan peta hash!