Menentukan Transisi DP

Setelah state dirancang, langkah berikutnya adalah menentukan transisi: bagaimana kita berpindah dari satu state ke state lain, dan berapa biaya atau nilai yang dihasilkan. Transisi adalah jantung dari recurrence DP. Pertanyaan kuncinya: pada state ini, pilihan apa yang tersedia dan apa konsekuensinya? Pada Chapter ini kita akan mempelajari pola-pola transisi umum, cara menulis recurrence dari pilihan ke rumus matematika, serta contoh konkret pada masalah klasik.

Aturan: Pilihan pada Setiap State #

Setiap state biasanya menawarkan beberapa pilihan. DP mengevaluasi semua pilihan dan memilih yang terbaik (maksimum/minimum) atau menjumlahkan semua (untuk menghitung jumlah cara).

Pola umum transisi:

1. Maksimum (optimasi): dp[state] = max(dp[state1] + cost1, dp[state2] + cost2, ...).
2. Minimum (optimasi): sama dengan maksimum, dengan min.
3. Penjumlahan (counting): dp[state] = dp[state1] + dp[state2] + ....
4. Boole (feasibility): dp[state] = dp[state1] OR dp[state2] OR ....

Mekanisme: Dari Pilihan ke Rumus #

Cara menulis recurrence:

1. Identifikasi pilihan — apa yang bisa dilakukan pada state saat ini?
2. Tentukan konsekuensi — setiap pilihan membawa ke state mana, dengan biaya/nilai berapa?
3. Gabungkan — pakai max, min, +, atau OR tergantung tipe masalah.

Contoh: Knapsack 0/1 #

State: (i, w) — nilai maksimum mempertimbangkan item 0..i-1 dengan kapasitas w.

Pilihan pada state (i, w):

1. Lewati item i-1 → transisi ke (i-1, w), nilai dp[i-1][w].
2. Ambil item i-1 (jika w[i-1] <= w) → transisi ke (i-1, w - w[i-1]), nilai dp[i-1][w-w[i-1]] + v[i-1].

Recurrence:

dp[i][w] = max(dp[i-1][w], dp[i-1][w-w[i-1]] + v[i-1])   jika w[i-1] <= w
dp[i][w] = dp[i-1][w]                                     jika w[i-1] > w

Base case: dp[0][w] = 0 untuk semua w (tidak ada item → nilai 0).

Contoh: LCS #

State: (i, j) — LCS dari s[0..i-1] dan t[0..j-1].

Pilihan:

1. Bila s[i-1] == t[j-1]: kedua karakter cocok → dp[i-1][j-1] + 1.
2. Bila tidak cocok: skip salah satu → max(dp[i-1][j], dp[i][j-1]).

dp[i][j] = dp[i-1][j-1] + 1                          jika s[i-1] == t[j-1]
dp[i][j] = max(dp[i-1][j], dp[i][j-1])               jika tidak

Base case: dp[0][j] = 0 dan dp[i][0] = 0 (string kosong → LCS 0).

Contoh: Climbing Stairs #

State: dp[i] — jumlah cara untuk mencapai anak tangga i.

Pilihan: dari tangga i, kita bisa datang dari i-1 (1 langkah) atau i-2 (2 langkah).

dp[i] = dp[i-1] + dp[i-2]

Base case: dp[0] = 1, dp[1] = 1.

Kode: Climbing Stairs dengan Transisi Jelas #

#include <iostream>
#include <vector>

long long climb(int n) {
    if (n <= 1) return 1;
    std::vector<long long> dp(n + 1);
    dp[0] = 1;  // base: di tanah, 1 cara (tidak melompat)
    dp[1] = 1;  // base: 1 lompatan
    for (int i = 2; i <= n; ++i) {
        // Pilihan: datang dari i-1 (1 langkah) atau i-2 (2 langkah)
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

int main() {
    for (int n : {1, 3, 5, 10, 20}) {
        std::cout << "climb(" << n << ") = " << climb(n) << '\n';
    }
    return 0;
}

Output yang Dihasilkan:

climb(1) = 1
climb(3) = 3
climb(5) = 8
climb(10) = 89
climb(20) = 10946

1. Baris dp[0] = 1; dp[1] = 1;: dua base case. dp[0]=1 karena ada tepat satu cara untuk “tidak melompat” (di posisi awal).
2. Baris dp[i] = dp[i - 1] + dp[i - 2];: transisi inti. Jumlah cara untuk sampai i = jumlah cara untuk sampai i-1 (lalu 1 langkah) + jumlah cara untuk sampai i-2 (lalu 2 langkah).
3. Hasil climb(5) = 8: 8 cara untuk naik 5 tangga. Cocok dengan Fibonacci offset (fib(6) = 8).

Pola Transisi Umum #

Beberapa pola transisi muncul berulang pada masalah DP:

Kode: Longest Increasing Subsequence (O(n²)) #

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

int lis(const std::vector<int>& a) {
    int n = static_cast<int>(a.size());
    if (n == 0) return 0;
    // dp[i] = panjang LIS yang berakhir di indeks i
    std::vector<int> dp(n, 1);
    for (int i = 1; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
            // Pilihan: perpanjang LIS yang berakhir di j, jika a[j] < a[i]
            if (a[j] < a[i]) {
                dp[i] = std::max(dp[i], dp[j] + 1);
            }
        }
    }
    return *std::max_element(dp.begin(), dp.end());
}

int main() {
    std::vector<int> a = {3, 10, 2, 1, 20};
    std::cout << "LIS = " << lis(a) << '\n';
    return 0;
}

Output yang Dihasilkan:

LIS = 3

1. Baris std::vector<int> dp(n, 1);: setiap elemen sendiri adalah LIS sepanjang 1.
2. Baris for (int j = 0; j < i; ++j): coba semua predecessor j. Inilah “pilihan” pada state i.
3. Baris if (a[j] < a[i]): syarat transisi — hanya boleh perpanjang bila elemen naik.
4. Baris dp[i] = std::max(dp[i], dp[j] + 1);: ambil best dari semua predecessor yang valid.
5. Hasil 3: LIS {3, 10, 20} atau {2, ...} → panjang 3. Sesuai.

Validasi Recurrence: Tiga Cek #

Sebelum mengimplementasikan DP, cek tiga hal:

1. Base case benar: apakah state terkecil punya nilai yang sudah jelas?
2. Urutan evaluasi: apakah setiap transisi merujuk ke state yang sudah dihitung?
3. Tidak ada state tak terdefinisi: setiap transisi harus menghasilkan state valid (cek boundary).

Ringkasan #

• Transisi = pilihan yang tersedia pada setiap state dan konsekuensinya.
• Pola umum: maksimum (optimasi), minimum, penjumlahan (counting), boolean (feasibility).
• Tulis recurrence dengan urutan: identifikasi pilihan → tentukan konsekuensi → gabungkan.
• Pola berulang: pilihan biner, akumulasi, best of predecessors, match/mismatch, komposisi rentang.
• Selalu validasi: base case, urutan evaluasi, dan tidak ada state tak terdefinisi.