Menguasai Pemrograman Dinamis: Panduan Lengkap dan Contoh Soal OSN Informatika SMA

Bagi para pejuang Olimpiade Sains Nasional (OSN) bidang Informatika, materi Pemrograman Dinamis (Dynamic Programming atau DP) sering kali menjadi momok yang menakutkan. DP dikenal sebagai salah satu topik tingkat lanjut (advanced) yang kerap menjadi pembeda antara peserta yang berhasil membawa pulang medali dan yang tidak.

Namun, benarkah Pemrograman Dinamis sesulit itu? Jawabannya: tidak selalu. Dengan memahami konsep dasar, mengenali pola masalah, dan banyak berlatih contoh soal, Anda bisa menaklukkan materi ini.

Artikel ini akan mengupas tuntas apa itu Pemrograman Dinamis, strategi penyelesaiannya, serta contoh soal DP standar OSN Informatika SMA lengkap dengan pembahasannya.

Apa Itu Pemrograman Dinamis (Dynamic Programming)?

Secara sederhana, Pemrograman Dinamis adalah teknik pemecahan masalah dengan cara memecah masalah besar menjadi sub-masalah yang lebih kecil, menyelesaikan sub-masalah tersebut sekali saja, lalu menyimpan hasilnya agar tidak perlu dihitung kembali di kemudian hari.

Prinsip utama dari DP adalah “mengingat masa lalu”. Strategi ini sangat efektif untuk menyelesaikan masalah optimasi (mencari nilai maksimum atau minimum) yang memiliki dua karakteristik utama:

Overlapping Subproblems: Sub-masalah yang sama dihitung berulang-ulang jika menggunakan metode biasa (seperti rekursi biasa).
Optimal Substructure: Solusi optimal dari masalah utama dapat dibentuk dari solusi optimal sub-masalahnya.

Dua Pendekatan dalam Pemrograman Dinamis

Dalam mengimplementasikan DP, ada dua pendekatan yang bisa digunakan:

Top-Down (Memoization): Memulai dari masalah utama, lalu memecahnya secara rekursif. Hasil dari setiap sub-masalah disimpan (biasanya dalam array atau hash map) agar bisa langsung diambil jika dibutuhkan lagi.
Bottom-Up (Tabulation): Memulai dari sub-masalah terkecil (kasus dasar/ base case), lalu mengisi tabel secara berurutan hingga mencapai solusi untuk masalah utama. Pendekatan ini biasanya menggunakan perulangan (looping).

Langkah-Langkah Menyelesaikan Soal DP OSN

Saat menghadapi soal OSN Informatika yang membutuhkan solusi DP, jangan langsung menulis kode. Ikuti langkah-langkah sistematis berikut:

Definisikan State: Tentukan apa arti dari indeks array DP Anda. Misalnya, dp[i] menyatakan keuntungan maksimum yang bisa didapat hingga elemen ke-i.
Tentukan Base Case: Cari nilai awal yang sudah pasti dan tidak membutuhkan perhitungan (misal: dp[0] = 0).
Rumuskan Transisi State (State Transition): Ini adalah jantung dari DP. Temukan rumus matematis yang menghubungkan dp[i] dengan nilai-nilai DP yang sudah dihitung sebelumnya (seperti dp[i-1], dp[i-2], dsb).
Tentukan Hasil Akhir: Di mana jawaban dari masalah utama disimpan? Apakah di dp[N], atau nilai maksimum dari seluruh isi array DP?

Contoh Soal 1: Katak Lompat (Frog Jump)

Mari kita mulai dengan contoh soal klasik yang sangat sering muncul dengan berbagai variasi di OSN tingkat kabupaten maupun provinsi.

Deskripsi Soal

Terdapat $N$ buah batu yang berjejer dari 1 hingga $N$. Setiap batu ke-$i$ memiliki ketinggian $H_i$. Seekor katak berada di batu 1 dan ingin pergi ke batu $N$.

Jika katak berada di batu $i$, ia dapat melompat ke batu $i+1$ atau batu $i+2$. Biaya energi yang dihabiskan untuk melompat dari batu $i$ ke batu $j$ adalah $|H_i – H_j|$ (nilai mutlak dari selisih ketinggian).

Tentukan biaya energi minimum yang didekatkan katak untuk mencapai batu $N$.

Format Input:

baris pertama berisi $N$ ($2 \le N \le 10^5$).
baris kedua berisi $N$ buah bilangan bulat $H_1, H_2, \dots, H_N$.

Contoh Input:

Plaintext

4
10 30 40 20

Contoh Output:

Plaintext

Penjelasan: Katak melompat dari batu 1 ke batu 2 (biaya: $|10-30| = 20$), lalu dari batu 2 ke batu 4 (biaya: $|30-20| = 10$). Total energi = $20 + 10 = 30$.

Pembahasan dan Solusi DP

Kita akan menyelesaikan soal ini dengan pendekatan Bottom-Up (Tabulation).

Definisikan State: dp[i] = Energi minimum yang dibutuhkan untuk mencapai batu ke-i.
Base Case: * dp[1] = 0 (Katak sudah berada di batu 1, tidak butuh energi).
- dp[2] = |H_1 - H_2| (Hanya ada satu cara mencapai batu 2, yaitu melompat dari batu 1).
Transisi State: Untuk mencapai batu $i$ ($i \ge 3$), katak bisa datang dari batu $i-1$ atau batu $i-2$. Kita ambil nilai minimumnya:$$dp[i] = \min(dp[i-1] + |H_i – H_{i-1}|, dp[i-2] + |H_i – H_{i-2}|)$$

Kode Implementasi (C++)

Berikut adalah kode standar yang biasa digunakan dalam kompetisi pemrograman seperti OSN:

C++

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;

int main() {
    int N;
    cin >> N;
    vector<int> H(N + 1);
    for (int i = 1; i <= N; i++) {
        cin >> H[i];
    }

    vector<int> dp(N + 1, 0);
    
    // Base cases
    dp[1] = 0;
    dp[2] = abs(H[2] - H[1]);

    // Mengisi tabel DP
    for (int i = 3; i <= N; i++) {
        int opsi1 = dp[i-1] + abs(H[i] - H[i-1]);
        int opsi2 = dp[i-2] + abs(H[i] - H[i-2]);
        dp[i] = min(opsi1, opsi2);
    }

    // Hasil akhir berada di dp[N]
    cout << dp[N] << endl;

    return 0;
}

Contoh Soal 2: Mencuri Emas (Knapsack Problem tanpa Bobot)

Soal ini merupakan variasi dari Subset Sum Problem atau 0/1 Knapsack yang menguji logika optimasi Anda.

Deskripsi Soal

Seorang pencuri masuk ke dalam gudang yang berisi $N$ buah bongkahan emas. Emas ke-$i$ memiliki berat $W_i$ kg. Pencuri tersebut membawa tas yang hanya mampu menampung beban maksimal seberat $K$ kg. Pencuri ingin membawa pulang emas dengan total berat semaksimal mungkin tanpa melebihi kapasitas tasnya.

Format Input:

Baris pertama berisi dua bilangan bulat, $N$ dan $K$ ($1 \le N \le 100$, $1 \le K \le 10.000$).
Baris berikutnya berisi $N$ bilangan bulat yang menyatakan berat masing-masing emas.

Contoh Input:

Plaintext

4 15
3 5 7 8

Contoh Output:

Plaintext

Penjelasan: Pencuri dapat memilih emas dengan berat 7 dan 8. Total beratnya adalah $7 + 8 = 15$, yang pas dengan kapasitas tas.

Pembahasan dan Solusi DP

Masalah ini tidak bisa diselesaikan dengan algoritma Greedy (mengambil yang paling berat atau paling ringan dulu), melainkan harus menggunakan DP.

Definisikan State: dp[i][j] = Berat maksimum yang bisa didapatkan menggunakan pilihan emas dari indeks 1 sampai i dengan kapasitas tas sebesar j.
Base Case: Jika kapasitas tas j = 0 atau pilihan emas tidak ada (i = 0), maka dp[i][j] = 0.
Transisi State: Untuk emas ke-i dengan berat $W_i$:
- Jika $W_i > j$ (emas terlalu berat), kita tidak bisa mengambilnya: dp[i][j] = dp[i-1][j].
- Jika $W_i \le j$, kita punya dua pilihan: tidak mengambilnya atau mengambilnya. Kita pilih yang menghasilkan nilai terbesar:$$dp[i][j] = \max(dp[i-1][j], dp[i-1][j – W_i] + W_i)$$

Kode Implementasi (C++)

C++

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int N, K;
    cin >> N >> K;
    vector<int> W(N + 1);
    for (int i = 1; i <= N; i++) {
        cin >> W[i];
    }

    // Membuat matriks DP berukuran (N+1) x (K+1) diisi dengan 0
    vector<vector<int>> dp(N + 1, vector<int>(K + 1, 0));

    for (int i = 1; i <= N; i++) {
        for (int j = 0; j <= K; j++) {
            if (W[i] > j) {
                dp[i][j] = dp[i-1][j]; // Tidak muat
            } else {
                dp[i][j] = max(dp[i-1][j], dp[i-1][j - W[i]] + W[i]); // Muat
            }
        }
    }

    cout << dp[N][K] << endl;

    return 0;
}

Kesimpulan dan Tips Latihan OSN

Menguasai Pemrograman Dinamis membutuhkan ketekunan dan ketajaman logika. Trik terbesar dalam DP bukanlah menulis kodenya, melainkan menemukan rumus transisinya.

Bagi Anda yang sedang bersiap menghadapi OSN Informatika SMA, berikut beberapa tips tambahan:

Sering berlatih di Online Judge: Kunjungi platform seperti TLX Toki (sangat direkomendasikan untuk kurikulum OSN), Codeforces, atau AtCoder (cari AtCoder Beginner Contest bagian DP).
Mulai dari yang mudah: Kuasai variasi soal Fibonacci, Coin Change, Longest Increasing Subsequence (LIS), dan Knapsack sebelum mencoba soal DP dengan teknik Bitmask atau Tree DP.
Analisis Kompleksitas: Selalu pastikan ukuran array DP dan perulangan Anda tidak melewati batas waktu (biasanya $10^8$ operasi per detik) dan batas memori yang ditentukan di soal.