Memoisasi tanpa Rekursi
Pelajaran 5 dari 15 dalam kursus Dasar-Dasar Pemrograman Dinamis di Coddy.
Pada pelajaran sebelumnya, kita mempelajari memoization dan bagaimana teknik ini dapat membantu meningkatkan kompleksitas waktu solusi rekursif kita. Dalam pelajaran ini, kita akan mempelajari cara menggunakan rekursi dengan memoization untuk menyelesaikan masalah dengan lebih efisien.
Rekursi adalah teknik dalam pemrograman ketika sebuah fungsi memanggil dirinya sendiri untuk menyelesaikan masalah. Solusi rekursif bisa sangat elegan dan intuitif, tetapi juga bisa tidak efisien, terutama jika fungsi yang sama dipanggil beberapa kali dengan argumen yang sama. Di sinilah memoization berperan. Dengan menyimpan hasil pemanggilan fungsi sebelumnya, kita dapat menghindari perhitungan berulang dan meningkatkan performa solusi rekursif secara signifikan.
Tantangan
MudahMisalkan kamu bisa menaiki 1 anak tangga atau 2 anak tangga sekaligus.
Tulis fungsi bernama count_ways yang menerima bilangan bulat n dan mengembalikan jumlah cara untuk menaiki tangga dengan n anak tangga.
Fungsi tersebut harus menggunakan memoization untuk menghindari perhitungan berulang.
Hindari menggunakan rekursi dalam tantangan ini!
Coba sendiri
def count_ways(n):
# TODO: tulis kodemu di siniSemua pelajaran di Dasar-Dasar Pemrograman Dinamis
3Algoritma pemrograman dinamis
Subsekuens bersama terpanjangMasalah knapsackMasalah penukaran koinJarak editLatihan sendiri: Compiler Python online