Modul ini memperkenalkan dua pendekatan penyelesaian soal optimasi yang saling melengkapi, yaitu strategi greedy beserta batas kegagalannya, lalu pemrograman dinamis (dynamic programming, DP) dari fondasinya sampai kerangka pengerjaan soal baru. Materi dimulai dari argumen penukaran dan contoh tandingan ketika pilihan lokal menyesatkan, berlanjut ke submasalah tumpang-tindih, memoisasi, tabel bottom-up, DP satu dan dua dimensi, hingga kerangka empat langkah untuk merumuskan state, transisi, basis, dan urutan pengisian. Setiap soal diimplementasikan pada Python dan Java dengan tabel dp yang dicetak pada keluaran, sehingga mekanisme pengisiannya terbaca langsung. Modul ini bertumpuk pada rekursi dan pengurutan dari modul-modul sebelumnya, sekaligus menjadi puncak teknis jalur ini.
Greedy dan pemrograman dinamis
Modul greedy dan DP: argumen penukaran, memoisasi, DP 1D dan 2D, hingga kerangka penyelesaian soal DP.
0/0 selesai
- Strategi greedy
Argumen penukaran pada pilihan lokal dan kondisi ketika greedy gagal.
- Dasar-dasar DP
Submasalah tumpang-tindih, memoisasi top-down, dan tabel bottom-up.
- DP satu dimensi
Menanjak tangga, perampok rumah, dan pertukaran koin dengan DP satu dimensi.
- DP dua dimensi
Lintasan kisi, knapsack, dan longest common subsequence dengan tabel dua dimensi.
- Kerangka penyelesaian soal DP
Menentukan state, transisi, basis, dan urutan pengisian pada soal DP baru.