Scribd
Unggah
8 tayangan6 halaman

Panduan Teknik Dynamic Programming

Diunggah oleh

aliqbalamin
Hak Cipta
© All Rights Reserved
Kami menangani hak cipta konten dengan serius. Jika Anda merasa konten ini milik Anda, ajukan klaim di sini.
Format Tersedia
Unduh sebagai PPTX, PDF, TXT atau baca online di Scribd
8 tayangan6 halaman

Panduan Teknik Dynamic Programming

Diunggah oleh

aliqbalamin
Hak Cipta
© All Rights Reserved
Kami menangani hak cipta konten dengan serius. Jika Anda merasa konten ini milik Anda, ajukan klaim di sini.
Format Tersedia
Unduh sebagai PPTX, PDF, TXT atau baca online di Scribd

Dynamic Programming (DP)

• Teknik untuk memecahkan masalah kompleks


dengan membaginya menjadi sub-masalah
lebih kecil.
• Tujuan: mendapatkan solusi optimal dan
menghindari perhitungan berulang.
• Konsep inti: Memoization & Tabulation.
Karakteristik Masalah DP

• 1. Masalah terbagi menjadi beberapa tahap


(stage).
• 2. Setiap tahap memiliki status (state)
tertentu.
• 3. Keputusan mengubah state tahap
berikutnya.
• 4. Ongkos meningkat seiring pertambahan
tahap.
• 5. Ongkos bergantung pada tahap
Forward / Bottom-Up Approach

• Mulai dari submasalah paling kecil → besar.


• Menggunakan tabulation (tabel).
• Tidak menggunakan rekursi.
• Perhitungan berurutan dan efisien.
Cara Kerja Bottom-Up

• 1. Identifikasi submasalah terkecil.


• 2. Hitung berurutan dari kecil → besar.
• 3. Simpan nilai tiap submasalah.
• 4. Gunakan tabel untuk solusi akhir.
Backward / Top-Down Approach

• Mulai dari masalah terbesar.


• Gunakan rekursi + memoization.
• Hanya menghitung submasalah yang
diperlukan.
• Lebih intuitif dalam pemecahan.
Cara Kerja Top-Down

• 1. Mulai dari masalah besar (misal F(n)).


• 2. Pecah ke submasalah lebih kecil.
• 3. Jika sudah dihitung, ambil dari memo.
• 4. Jika belum, hitung lalu simpan.
• 5. Berhenti saat mencapai basis.

Anda mungkin juga menyukai