DYNAMIC PROGRAMMING (DP)

Berbeda dengan Greedy, Dynamic Programming menguji semua kemungkinan solusi secara cerdas dengan memecah masalah menjadi sub-masalah yang tumpang tindih. Karakteristik utama DP:

1. Overlapping Subproblems (Sub-masalah Tumpang Tindih)

Masalah utama dapat diuraikan menjadi sub-masalah yang lebih kecil, dan sub-masalah yang sama persis dipanggil dan dihitung berulang kali dalam struktur pohon keputusan/rekursi.

2. Optimal Substructure (Substruktur Optimal)

Solusi optimal dari masalah besar mengandung solusi optimal dari sub-masalahnya.

A. Teknik Utama DP: Memorisasi Vs Tabulasi

Untuk mengeliminasi perhitungan berulang, Dynamic Programming mencatat hasil perhitungan sub-masalah ke dalam tempat penyimpanan (tabel/array). Terdapat dua pendekatan teknis:

1. Memorasi (Top-Down)

- Memulai dari masalah utama n.

- Menggunakan Rekursi + Tabel Memo.

- Menghitung sub-masalah hanya saat dibutuhkan.

2. Tabulasi (Bottom-UP)

- Memulai dari kasus dasar (base cases) paling bawah.

- Menggunakan Perulangan (Looping) + Tabel 1D/2D secara sekuensial.

B. Studi Kasus 2: Optimasi Kehidupan Sehari-Hari (Penukaran Uang Koin)

Seorang kasir ingin memberikan kembalian belanja sebesar V = 6 rupiah. Pecahan koin yang tersedia adalah {1, 3, 4}. Berapakah jumlah koin minimum yang harus diberikan?

1. Teknik Memorisasi

Analogi: Kamu adalah seorang kasir yang malas menghitung ulang hal yang sama. Setiap kali mendapat jawaban untuk angka tertentu, kamu langsung mencatatnya di Buku Memo.

a. Memulai dari Target Utama (Uang 6 Rupiah):

Kamu ingin tahu: "Berapa koin minimal untuk membuat 6 rupiah?"
Untuk menjawabnya, kamu mencoba memilih koin pertama yang mungkin:

Jika ambil koin 1: Sisa uang jadi 5.
Jika ambil koin 3: Sisa uang jadi 3.
Jika ambil koin 4: Sisa uang jadi 2.

Menelusuri Cabang (Tanya ke Bawah):

Kamu fokus ke jalur pertama dulu (sisa 5). Untuk menyelesaikan sisa 5, kamu menelusuri koin 1, 3, dan 4 lagi hingga sampai ke titik dasar (0 rupiah = 0 koin).
Saat memproses sisa 3 rupiah, kamu menemukan bahwa pilihan terbaik untuk membuat 3 rupiah adalah langsung mengambil 1 koin pecahan 3.

o Langkah Penting (Mencatat): Sebelum lanjut, kamu langsung menulis di Buku Memo:

"Catatan: Sisa uang 3 rupiah butuh minimal 1 koin."

c. Mencontek Catatan (Mencegah Hitung Ulang):

Saat kamu kembali ke target awal (6) dan ingin mencoba Jalur Kedua (ambil koin 3), sisa uangmu menjadi 3 rupiah.
Kali ini kamu tidak perlu menghitung ulang dari awal untuk angka 3! Kamu tinggal membuka Buku Memo, melihat bahwa angka 3 cuma butuh 1 koin, lalu selesai.

d. Mengambil Keputusan Akhir:

Kamu membandingkan hasil akhir dari ketiga pilihan koin pertama:

o Pakai koin 1 di awal à butuh 3 koin total.

o Pakai koin 3 di awal à butuh 2 koin total.

o Pakai koin 4 di awal à butuh 3 koin total.

Hasil paling sedikit adalah 2 koin (koin 3 + 3).

2. Teknik Tabulasi (Bottom-Up: Dari Angka Nol Naik ke Atas)

Analogi: Kamu tidak suka menebak-nebak atau bercabang. Kamu memilih membangun Tabel Jawaban secara sistematis, diisi urut satu per satu dari angka 0, 1, 2, 3, 4, 5, hingga 6.

Mengisi Angka Paling Dasar (Uang 0):

Kamu tahu pasti bahwa kembalian 0 rupiah membutuhkan 0 koin. Ini jadi fondasi awal tabelmu.

Mengisi Angka 1 dan 2 Secara Berurutan:

Uang 1: Pilihan koin hanya 1. Ambil koin 1, sisa uang 0. Kamu intip tabel nilai 0 (nilainya 0). Jadi, 1 + 0 = 1 koin.
Uang 2: Pilihan koin hanya 1. Ambil koin 1, sisa uang 1. Kamu intip tabel nilai 1 (nilainya 1). Jadi, 1 + 1 = 2 koin.

Mengisi Angka 3 (Mulai Membandingkan):

Untuk uang 3, ada dua pilihan koin yang muat (1 dan 3):

Ambil koin 1 à sisa 2. Lihat tabel nilai 2 (nilainya 2) à 1 + 2 = 3 koin.
Ambil koin 3 à sisa 0. Lihat tabel nilai 0 (nilainya 0) à 1 + 0 = 1 koin.
Kamu pilih nilai terkecil: 1 koin. Tulis angka 1 di kotak tabel angka 3.

Melanjutkan Pengisian (Angka 4 dan 5):

Uang 4: Kamu bandingkan opsi koin 1, 3, dan 4. Pilihan koin 4 memberikan hasil paling kecil, yaitu 1 + {tabel}[0] = 1 koin.
Uang 5: Kamu bandingkan koin 1, 3, dan 4 dengan mengintip tabel angka 4, 2, dan 1. Paling kecil menghasilkan 2 koin.

Mencapai Target Akhir (Angka 6):

Saat mengisi kotak target 6, kamu tinggal membandingkan 3 opsi koin pertama menggunakan data tabel yang sudah pasti benar di kotak-kotak sebelumnya: