DP satu dimensi

DP satu dimensi adalah pola pemrograman dinamis yang menyimpan jawabannya pada tabel dp berindeks tunggal. Sel dp[i] merangkum jawaban untuk prefiks masukan sepanjang i, yaitu i elemen pertama dari masukan. Tabel semacam ini cukup untuk banyak soal klasik yang keputusannya bergerak dari ujung ke ujung deret. Topik ini mengerjakan tiga soalnya satu per satu, yaitu menghitung cara menanjak tangga, memaksimalkan hasil perampok rumah, dan meminimumkan jumlah koin, lengkap dengan tabel yang dicetak pada keluaran.

Menanjak tangga#

Soalnya menghitung banyak cara mencapai anak tangga ke-n bila setiap langkah hanya boleh menaiki satu atau dua anak tangga. Kuncinya menatap langkah terakhir saja. Bila cara-cara menuju tangga ke-i dikelompokkan menurut langkah terakhirnya, ada yang datang dari tangga ke-i-1 dengan satu langkah dan ada yang datang dari tangga ke-i-2 dengan dua langkah, tanpa ada yang tertinggal di antara keduanya. Jadi kedua kelompok itu tinggal dijumlahkan:

Nilai dp[0] = 1 bukan angka karangan, melainkan satu cara berdiri di dasar tanpa melangkah sama sekali, dan nilai inilah yang membuat rumusnya berlaku tanpa kasus khusus dari awal sampai akhir. Tidak ada kandidat lain yang perlu ditimbang karena langkahnya memang hanya dua kemungkinan. Pola dua pintu masuk inilah yang membedakan soal tangga dari soal koin pada bagian berikutnya, karena soal koin harus membandingkan setiap pecahan.

"""Menanjak tangga: menghitung banyak cara mencapai anak tangga ke-n."""

def cara_tangga(n):
    dp = [0] * (n + 1)
    dp[0] = 1                       # satu cara berada di dasar: tidak melangkah
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp

dp = cara_tangga(10)
print("n   :", list(range(11)))
print("cara:", dp)
print("cara naik 10 anak :", dp[10])

n   : [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
cara: [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89]
cara naik 10 anak : 89

Tabelnya berbunyi 1, 1, 2, 3, 5, 8, dan seterusnya, deret Fibonacci yang sudah dikenal. Kemiripan itu wajar karena aturan tangga dan aturan Fibonacci memang sama, yaitu nilai baru dijumlahkan dari dua nilai sebelumnya. Aturan yang identik membuat satu soal menyamar menjadi soal lain hanya karena bunyinya berbeda. Angka 89 di ujung tabel adalah jawaban soal 10 anak tangga, dan setiap nilai di kirinya menjadi bahan mentah untuk menghitung nilai berikutnya.

Perampok rumah#

Soal perampok rumah (house robber) memberi deretan rumah beserta nilai isinya, lalu melarang mengambil dua rumah bersebelahan dalam satu malam. Keputusan di rumah terakhir hanya punya dua kemungkinan. Mengambil rumah itu berarti rumah sebelumnya pasti dilewati, sehingga hasilnya nilai rumah ditambah jawaban hingga dua rumah sebelumnya. Melewatinya berarti jawabannya persis jawaban hingga rumah sebelumnya. Jalan terbaik adalah yang lebih besar di antara keduanya:

Tabel dp sengaja dibuat satu sel lebih panjang daripada deret rumah, dengan dp[0] = 0 untuk nol rumah dan dp[1] = nilai[0] untuk satu rumah, sehingga rumusnya berlaku seragam tanpa kasus khusus.

"""Perampok rumah: nilai maksimum tanpa mengambil dua rumah bersebelahan."""

nilai_rumah = [3, 2, 5, 10, 7]

def rob(nilai):
    n = len(nilai)
    dp = [0] * (n + 1)      # dp[i]: nilai maksimum untuk i rumah pertama
    dp[1] = nilai[0]
    for i in range(2, n + 1):
        dp[i] = max(dp[i - 1], dp[i - 2] + nilai[i - 1])
    return dp

dp = rob(nilai_rumah)
print("rumah :", nilai_rumah)
print("dp    :", dp)
print("nilai maksimum:", dp[-1])

rumah : [3, 2, 5, 10, 7]
dp    : [0, 3, 3, 8, 13, 15]
nilai maksimum: 15

Tabelnya bisa diperiksa sel demi sel dengan rumus. dp[4] = 15 lahir dari dp[2] + 7 = 8 + 7, artinya rumah bernilai 7 memang diambil, sedangkan dp[3] = 13 lahir dari dp[1] + 10 = 3 + 10. Kombinasi menang akhirnya adalah rumah bernilai 3, 5, dan 7 yang masing-masing tidak bersebelahan, dan jawaban 15 itu tidak akan ditemukan dengan mengambil rumah bernilai besar secara serakah.

Pertukaran koin minimum#

Soal ketiga mencari jumlah koin paling sedikit untuk mencapai sebuah nilai. Tandingan pada topik strategi greedy memperlihatkan kriteria koin terbesar yang meleset untuk pecahan 1, 3, 4, dan tabel dp di sini menjelaskan mengapa DP selalu menemukan jawaban minimum. Koin terakhir yang dipakai bisa berupa pecahan mana pun, sehingga setiap pecahan p memberi kandidat dp[n-p] + 1, dan yang terkecil dimenangkan:

"""Pertukaran koin minimum dengan DP satu dimensi."""

pecahan = [1, 3, 4]

def koin_minimum(nilai):
    dp = [0] + [999] * nilai    # 999 berarti "belum ada cara" pada tahap ini
    asal = [0] * (nilai + 1)
    for n in range(1, nilai + 1):
        for p in pecahan:
            if p <= n and dp[n - p] + 1 < dp[n]:
                dp[n] = dp[n - p] + 1
                asal[n] = p     # catat koin terakhir yang dipakai
    koin, sisa = [], nilai
    while sisa > 0:
        koin.append(asal[sisa])
        sisa -= asal[sisa]
    return dp, koin

dp, koin = koin_minimum(6)
print("n      :", list(range(7)))
print("dp     :", dp)
print("koin 6 :", koin, "(", len(koin), "koin )")

n      : [0, 1, 2, 3, 4, 5, 6]
dp     : [0, 1, 2, 1, 1, 2, 2]
koin 6 : [3, 3] ( 2 koin )

Tabel terbaca langsung, yaitu dp[6] = 2, dan array asal merekonstruksi koinnya mundur menjadi 3 lalu 3, pasangan yang dilewatkan greedy. Tabel ini juga membeberkan sebab kegagalan greedy, karena koin terakhir tidak dipilih dengan menatap pecahan terbesar semata, melainkan dengan menimbang kandidat dari setiap pecahan. Nilai 999 pada kode berperan sebagai angka yang pasti kalah, sehingga kandidat pertama selalu memenangkan perbandingan pertamanya tanpa percabangan tambahan.

Varian Java#

Ketiga soal di atas diterjemahkan ke Java dalam satu berkas dengan fungsi terpisah. Struktur tabelnya identik, perbedaannya hanya di sintaks, misalnya Math.max menggantikan fungsi max dan Arrays.fill yang mengisi rentang tertentu dengan nilai 999 sebagai penanda sementara.

import java.util.Arrays;

public class DpSatuDimensi {
    // tiga soal klasik DP satu dimensi: tangga, perampok, dan koin minimum

    static int[] tangga(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp;
    }

    static int[] perampok(int[] nilai) {
        int n = nilai.length;
        int[] dp = new int[n + 1];
        dp[1] = nilai[0];
        for (int i = 2; i <= n; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nilai[i - 1]);
        }
        return dp;
    }

    static int koinMinimum(int nilai) {
        int[] pecahan = {1, 3, 4};
        int[] dp = new int[nilai + 1];
        Arrays.fill(dp, 1, nilai + 1, 999);
        for (int n = 1; n <= nilai; n++) {
            for (int p : pecahan) {
                if (p <= n && dp[n - p] + 1 < dp[n]) {
                    dp[n] = dp[n - p] + 1;
                }
            }
        }
        return dp[nilai];
    }

    public static void main(String[] args) {
        System.out.println("cara tangga 10 : " + tangga(10)[10]);
        System.out.println("dp perampok    : " + Arrays.toString(perampok(new int[]{3, 2, 5, 10, 7})));
        System.out.println("koin minimum 6 : " + koinMinimum(6));
    }
}

cara tangga 10 : 89
dp perampok    : [0, 3, 3, 8, 13, 15]
koin minimum 6 : 2

Ketiga angkanya sama dengan versi Python, yaitu 89 cara, tabel perampok yang berakhir di 15, dan dua koin untuk nilai 6. Fungsi tangga dan perampok mengembalikan tabelnya, sehingga isi tabel dapat dicetak dan diperiksa per sel seperti pada versi Python, sedangkan koinMinimum hanya mengembalikan jawaban akhirnya. Perulangan koin di Java memakai bentuk for (int p : pecahan) yang setara dengan perulangan for p in pecahan pada Python, sehingga tiga rumus transisi yang sama terbaca nyaris serupa di kedua bahasa. Pada Arrays.fill(dp, 1, nilai + 1, 999), batas bawah 1 sifatnya inklusif dan batas atasnya eksklusif, sehingga dp[0] tetap nol sebagai basisnya. Penamaan fungsinya juga mengikuti soalnya masing-masing, sehingga main terbaca sebagai ringkasan tiga rumus transisi.

Kesalahan umum#

1. Mengisi dp[0] dengan 0 pada soal tangga. Angka itu berarti nol cara, padahal berdiri di dasar adalah satu cara, sehingga seluruh tabel tergeser dan jawabannya selalu kurang. Tulis arti setiap basis dalam satu kalimat sebelum mengetik kodenya.
2. Tertukar indeks tabel dan indeks masukan. Rumus perampok memakai nilai[i-1], bukan nilai[i], karena tabelnya satu sel lebih panjang. Keliru satu kali membuat tabel terlihat sah tetapi isinya bergeser diam-diam.
3. Melacak koin terpilih dengan menyalin daftar pada setiap sel. Waktu dan memorinya membengkak tanpa perlu. Catat array asal yang menyimpan koin terakhir per nilai, lalu susun mundur seperti pada contoh.
4. Menghitung ulang tabel untuk setiap pertanyaan nilai. Bila banyak nilai akan ditanyakan pada pecahan yang sama, tabel dp cukup dihitung sekali sampai nilai terbesarnya. Setiap pertanyaan kemudian tinggal membaca satu sel, pola yang sama dengan jumlah prefiks, yaitu penjumlahan kumulatif dari awal deret. Menghitung ulang per pertanyaan membuang seluruh pekerjaan tabel yang sudah selesai.

Ringkasan#

• Sel dp[i] merangkum jawaban prefiks sepanjang i, dan transisinya menatap satu sampai dua sel sebelumnya.
• Tangga memakai dp[i] = dp[i-1] + dp[i-2], deret Fibonacci yang menyamar sebagai soal tangga.
• Perampok memakai dp[i] = max(dp[i-1], dp[i-2] + nilai[i-1]), dengan jawaban 15 untuk deret 3, 2, 5, 10, 7.
• Koin memakai dp[n] = 1 + min dp[n-p] dan array asal untuk merekonstruksi daftar koinnya.

Referensi#

• Change-making problem — Wikipedia — soal pertukaran koin minimum, sifat sistem pecahan kanonik, dan mengapa pecahan sembarang menuntut DP.
• Dynamic programming — Wikipedia — kerangka umum DP dengan tabel yang diisi dari basis menuju jawaban.