Optimasi ruang
Pelajaran 12 dari 15 dalam kursus Dasar-Dasar Pemrograman Dinamis di Coddy.
Dalam pemrograman dinamis, kita sering menggunakan tabel atau matriks untuk menyimpan solusi bagi submasalah. Namun, dalam beberapa kasus, ukuran tabel bisa terlalu besar dan menghabiskan terlalu banyak memori. Di sinilah optimasi ruang digunakan. Teknik optimasi ruang digunakan untuk mengurangi memori yang diperlukan untuk menyelesaikan masalah pemrograman dinamis.
Salah satu teknik optimasi ruang yang populer adalah menggunakan array bergulir, yang juga dikenal sebagai array geser. Alih-alih menyimpan seluruh tabel, hanya sebagian darinya yang disimpan pada satu waktu, dan nilai sebelumnya dibuang saat nilai baru dihitung. Teknik ini dapat mengurangi secara signifikan memori yang diperlukan untuk menyelesaikan masalah.
Tantangan
SulitDalam tantangan ini, kamu diberikan sebuah array bilangan bulat. Tugasmu adalah mencari panjang subsekuens meningkat terpanjang (LIS) dalam array tersebut. Subsekuens meningkat adalah rangkaian angka dalam array dengan setiap angka lebih besar daripada angka sebelumnya. LIS adalah subsekuens terpanjang seperti itu. Kamu harus menerapkan solusi menggunakan teknik optimasi ruang.
Coba sendiri
def lis_length(arr):
# Tulis kodemu di siniSemua pelajaran di Dasar-Dasar Pemrograman Dinamis
3Algoritma pemrograman dinamis
Subsekuens bersama terpanjangMasalah knapsackMasalah penukaran koinJarak editLatihan sendiri: Compiler Python online