Baca tanpa iklan
Misalnya, saat menghitung L(25), kita bisa menggunakan jalur langkah:
25 → 24 → 8 → 4 →…
Atau
25 → 24 →12 → 4 → …
Sehingga nilai L(4) dapat dihitung beberapa kali. Ini yang harus dihindari pada penyelesaian soal dengan teknik DP, yaitu dengan menggunakan tabel memoisasi. Dengan tabel memoisasi, kita dapat menyimpan nilai L yang sudah dihitung dan menggunakannya untuk menghitung nilai-nilai L yang lebih besar.
Berikut ini adalah langkah-langkah yang kita lakukan:
Pertama, simpan nilai L(1) = 0 (tidak perlu melakukan apa-apa).
Untuk setiap nilai n selanjutnya, ambil 3 buah nilai:
● A = L(n – 1) dari tabel memoisasi.
● Jika n habis dibagi 2, ambil nilai B = L(n/2) dari tabel memoisasi.
● Jika n habis dibagi 2, catat pula C = L(n/3) dari tabel memoisasi
Kemudian, ambil nilai terkecil dari A, B dan C. Misalkan hasilnya adalah D.
Maka, selanjutnya, isikan pada tabel memoisasi, nilai L(n) = D + 1.
Perhatikan bahwa untuk setiap nilai n, berlaku bahwa n – 1, n/2 (jika n habis dibagi 2) dan n/3 (jika n habis dibagi 3) adalah bilangan bulat positif yang lebih kecil dari n. Dengan demikian, kita yakin bahwa jika kita membangun tabel memoisasi ini dari bawah (bottom up), maka nilai A, B dan C pada langkah 2, 3 dan 4 di atas pasti sudah tersedia/terisi sebelumnya, sehingga tidak perlu kita hitung lagi.
Berikut ini adalah hasil tabel memoisasi yang dibangun dengan cara di
atas (sampai n = 25). Dari tabel tersebut, dapat disimpulkan bahwa jawaban
dari soal tersebut adalah L(25) = 5.
Disclaimer:
- Kunci jawaban Informatika di atas hanya digunakan oleh orang tua atau wali untuk memandu proses belajar anak.
- Sebelum melihat kunci jawaban, pastikan anak mengerjakan sendiri terlebih dahulu.
(Tribunnews.com/Rinanda)