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.

Dapatkan konten pendidikan mata pelajaran lainnya dari Kurikulum Merdeka dan Kurikulum 2013 dengan klik Di Sini.

Dapatkan juga berita penting dan informasi menarik lainnya dengan mengklik Google News.