13. Dynamic programming

Dynamic programming (DP) adalah cara menyelesaikan soal dengan memecahnya menjadi submasalah yang lebih kecil, menghitung setiap submasalah tepat sekali, dan menyimpan jawabannya untuk dipakai lagi.

Dua syarat sebuah soal bisa diselesaikan dengan DP:

1. Submasalah tumpang tindih. Submasalah yang sama muncul berkali-kali — seperti fib(43) yang dihitung ratusan juta kali di Bab 06.
2. Substruktur optimal. Jawaban terbaik untuk soal besar tersusun dari jawaban terbaik submasalahnya.

Cara paling ringkas untuk mengingat apa itu DP:

DP = brute force − pekerjaan yang terulang.

Bab 06 sudah memperlihatkan bedanya secara angka. fib(45) yang ditulis rekursif polos memerlukan 3.672.623.805 pemanggilan, padahal jawaban yang benar-benar berbeda hanya ada 46 buah: fib(0) sampai fib(45). Sisanya perhitungan ulang. Begitu setiap jawaban disimpan, pekerjaannya turun dari miliaran menjadi puluhan langkah — dan itulah seluruh isi gagasan DP.

Dua gaya penulisan

Top-down (memoization). Tulis rekursi biasa, lalu tambahkan ingatan. Sudah kamu kerjakan di tantangan Bab 06.

long long ingat[100];

long long fib(int n) {
    if (n <= 1) return n;
    if (ingat[n] != -1) return ingat[n];
    return ingat[n] = fib(n - 1) + fib(n - 2);
}

Bottom-up (tabulasi). Isi tabel dari submasalah terkecil ke terbesar, tanpa rekursi.

long long dp[100];

dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= n; i++) dp[i] = dp[i - 1] + dp[i - 2];

Keduanya menghitung hal yang sama:

Top-down lebih mudah ditulis dari rekursi yang sudah ada; bottom-up lebih cepat dan tidak berisiko kehabisan memori tumpukan. Buku ini memakai bottom-up untuk contoh-contoh berikutnya.

Lima langkah menyusun DP

Setiap kali menghadapi soal DP, jawab lima pertanyaan ini di kertas sebelum menulis kode:

1. Apa keadaannya (state)? Apa arti dp[i]? Tulis sebagai kalimat lengkap.
2. Apa kasus dasarnya? Keadaan terkecil yang jawabannya sudah diketahui.
3. Apa transisinya? Bagaimana dp[i] dihitung dari keadaan yang lebih kecil.
4. Urutan pengisiannya bagaimana? Setiap keadaan yang dipakai harus sudah terisi lebih dulu.
5. Jawabannya ada di keadaan mana?

Langkah 1 adalah yang tersulit, dan sisanya biasanya mengikuti.

Contoh 1: naik tangga

Ada tangga dengan n anak tangga. Sekali melangkah bisa naik 1 atau 2 anak tangga. Ada berapa cara berbeda mencapai anak tangga ke-n?

1. Keadaan. dp[i] = banyaknya cara mencapai anak tangga ke-i.
2. Kasus dasar. dp[0] = 1 (satu cara: diam di bawah), dp[1] = 1.
3. Transisi. Untuk sampai di i, langkah terakhirnya dari i − 1 atau dari i − 2. Jadi dp[i] = dp[i-1] + dp[i-2].
4. Urutan. Dari kecil ke besar.
5. Jawaban. dp[n].

dp[0] = 1;
dp[1] = 1;
for (int i = 2; i <= n; i++) dp[i] = dp[i - 1] + dp[i - 2];
cout << dp[n] << "\n";

Mengisi tabelnya untuk n = 6:

Periksa dengan tangan untuk i = 3: cara mencapai anak tangga ke-3 ada tiga, yaitu 1+1+1, 1+2, dan 2+1. Cocok dengan dp[3] = 3.

Hasilnya barisan Fibonacci lagi — pertanda bahwa banyak soal yang kelihatan berbeda sebenarnya berkeadaan sama.

Contoh 2: koin paling sedikit

Ini soal yang membuat greedy gagal di Bab 12.

Diberikan pecahan koin c[1..m] dan nilai k. Berapa koin paling sedikit untuk mencapai tepat k? Cetak -1 kalau tidak mungkin.

1. Keadaan. dp[v] = koin paling sedikit untuk membentuk nilai v.
2. Kasus dasar. dp[0] = 0.
3. Transisi. dp[v] = 1 + min(dp[v - c[i]]) untuk setiap koin c[i] yang tidak melebihi v.
4. Urutan. v dari 1 sampai k.
5. Jawaban. dp[k], atau -1 kalau nilainya masih tak terhingga.

const int BESAR = 1000000000;

dp[0] = 0;
for (int v = 1; v <= k; v++) {
    dp[v] = BESAR;
    for (int i = 0; i < m; i++) {
        if (v >= c[i] && dp[v - c[i]] + 1 < dp[v])
            dp[v] = dp[v - c[i]] + 1;
    }
}
cout << (dp[k] >= BESAR ? -1 : dp[k]) << "\n";

Mengisi tabelnya untuk koin {1, 3, 4}:

Cara membaca satu selnya: dp[6] memeriksa tiga kemungkinan koin terakhir — koin 1 memberi dp[5] + 1 = 3, koin 3 memberi dp[3] + 1 = 2, koin 4 memberi dp[2] + 1 = 3. Yang terkecil adalah 2, jadi dp[6] = 2.

Perhatikan bahwa DP tidak perlu tahu koin mana yang "sebaiknya" diambil lebih dulu. Ia mencoba semuanya sebagai koin terakhir, lalu memakai jawaban submasalah yang sudah terbukti terbaik. Di situlah letak perbedaannya dengan greedy, yang hanya mencoba satu pilihan dan tidak pernah mundur.

Jumlah langkahnya k × m: satu keadaan untuk tiap nilai, dan tiap keadaan memeriksa m koin. Untuk k = 10⁶ dan m = 10 itu 10 juta — cepat.

Bandingkan dengan greedy {1, 3, 4} dan k = 6: DP menjawab 2, greedy menjawab 3. DP memeriksa semua kemungkinan tanpa mengulang pekerjaan.

Contoh 3: knapsack 0/1

Ada n barang; barang ke-i beratnya w[i] dan nilainya v[i]. Tas hanya kuat menahan berat W. Setiap barang boleh diambil paling banyak sekali. Berapa nilai terbesar yang bisa dibawa?

1. Keadaan. dp[i][b] = nilai terbesar memakai i barang pertama dengan batas berat b.

2. Kasus dasar. dp[0][b] = 0 untuk semua b.

3. Transisi. Dua pilihan untuk barang ke-i:

   • tidak diambil: dp[i-1][b]
   • diambil (kalau b >= w[i]): dp[i-1][b - w[i]] + v[i]

   Ambil yang lebih besar.

4. Urutan. i dari 1 sampai n, b dari 0 sampai W.

5. Jawaban. dp[n][W].

for (int i = 1; i <= n; i++) {
    for (int b = 0; b <= W; b++) {
        dp[i][b] = dp[i - 1][b];                       // tidak diambil
        if (b >= w[i] && dp[i - 1][b - w[i]] + v[i] > dp[i][b])
            dp[i][b] = dp[i - 1][b - w[i]] + v[i];     // diambil
    }
}

Jumlah langkahnya n × W. Untuk n = 100 dan W = 10.000 itu sejuta.

Menelusuri untuk W = 5 dan tiga barang — (berat 2, nilai 3), (berat 3, nilai 4), (berat 4, nilai 5). Setiap baris adalah keadaan sesudah barang ke-i dipertimbangkan:

Jawabannya dp[3][5] = 7, yaitu barang pertama dan kedua (berat 2 + 3 = 5, nilai 3 + 4 = 7). Telusuri satu sel untuk memastikan paham: dp[2][5] memilih antara tidak mengambil barang kedua (dp[1][5] = 3) dan mengambilnya (dp[1][5-3] + 4 = dp[1][2] + 4 = 7). Yang lebih besar 7.

Perhatikan juga bahwa setiap baris hanya membaca baris tepat di atasnya. Sifat itu yang membuat tabel knapsack bisa dipadatkan menjadi satu baris saja untuk menghemat memori — teknik yang berguna saat n besar, tetapi tidak perlu dipakai sebelum versi dua dimensinya benar-benar dikuasai.

Menghitung jumlah langkah DP

Rumusnya selalu:

jumlah langkah = banyaknya keadaan × biaya satu transisi

Gunakan rumus itu bersama tabel batasan Bab 10: kalau banyaknya keadaan saja sudah 10¹⁰, keadaannya perlu dirancang ulang.

Mengenali soal DP

Empat tanda bahwa sebuah soal kemungkinan besar DP:

1. Soal menanyakan paling banyak, paling sedikit, atau berapa cara — bukan "cetak salah satu contoh".
2. Setiap langkah berupa pilihan (ambil atau tidak, langkah 1 atau 2, potong di sini atau tidak).
3. Brute force yang mencoba semua pilihan jelas benar, tetapi jumlah kemungkinannya 2ⁿ atau n!.
4. Pilihan yang sudah diambil mempengaruhi sisanya hanya lewat sedikit informasi — misalnya "sisa berat tas" atau "sudah sampai anak tangga ke berapa", bukan seluruh riwayat pilihan.

Tanda keempat yang paling menentukan, karena informasi sedikit itulah yang menjadi keadaan dp. Kalau sisa soal ternyata bergantung pada seluruh riwayat pilihan, keadaannya akan meledak dan soal itu bukan DP sederhana.

Perbandingan dengan dua cara sebelumnya:

Kesalahan yang paling sering

• Keadaan tidak didefinisikan sebagai kalimat. Kalau dp[i] tidak bisa dijelaskan dengan satu kalimat, transisinya pasti akan kacau.
• Kasus dasar salah. dp[0] = 0 dan dp[0] = 1 adalah dua soal berbeda: yang satu menghitung jumlah, yang lain mencacah cara.
• Urutan pengisian salah, sehingga keadaan yang dipakai belum terisi.
• Array kurang besar, sehingga jawaban untuk k terakhir tertimpa.

Pekerjaan rumah

Tips OSN

Tanda pertama soal DP: "berapa banyak cara", "paling sedikit", atau "paling besar", dengan pilihan yang bertumpuk. Kalau setiap langkah menghadirkan beberapa pilihan dan pilihan sekarang mempengaruhi pilihan berikutnya, greedy biasanya gagal dan DP biasanya berhasil.

Rumuskan keadaannya dalam satu kalimat sebelum menulis kode. Kalimat itu harus berbentuk "dp[...] adalah ... dari ... pertama". Kalau kalimatnya belum bisa ditulis, kodenya belum boleh ditulis. Hampir semua kesalahan DP lahir dari keadaan yang tidak jelas, bukan dari salah ketik.

Hitung ukuran tabelnya sebelum membuatnya. Jumlah keadaan dikalikan biaya per keadaan adalah jumlah langkahnya, dan jumlah keadaan dikalikan ukuran tipenya adalah memorinya:

Kalau tabelnya terlalu besar, sering kali hanya satu atau dua baris terakhir yang benar-benar diperlukan. Soal 2 di bawah adalah contohnya.

Periksa keadaan awal secara terpisah. Kesalahan paling sering pada DP bukan pada rumus perulangannya, melainkan pada nilai awal: dp[0] seharusnya 1 atau 0, batas atas seharusnya "tidak mungkin" bukan nol, dan petak pertama pada grid seharusnya diperiksa apakah terhalang.

Arah perulangan menentukan makna. Pada DP yang memakai satu array untuk menghemat memori, perulangan mundur berarti "setiap barang dipakai paling banyak sekali", sedangkan perulangan maju berarti "barang boleh dipakai berkali-kali". Dua soal yang berbeda, dua arah yang berbeda, kode yang hampir sama.

Uji DP dengan brute force. Untuk N ≤ 15, jawaban brute force pasti benar. Menjalankan keduanya pada ratusan masukan acak kecil menangkap kesalahan keadaan awal dan kesalahan batas yang tidak terlihat dari contoh soal.

Ringkasan

• DP adalah brute force dikurangi pekerjaan yang terulang: setiap submasalah dihitung tepat sekali dan jawabannya disimpan.
• Syaratnya submasalah tumpang tindih dan substruktur optimal.
• Dua gaya: top-down (rekursi + ingatan) dan bottom-up (mengisi tabel). Keduanya menghitung hal yang sama.
• Lima pertanyaan yang dijawab di kertas: keadaan, kasus dasar, transisi, urutan pengisian, letak jawaban. Keadaan harus bisa ditulis sebagai satu kalimat lengkap.
• Jumlah langkah = banyaknya keadaan × biaya satu transisi; bandingkan dengan tabel batasan Bab 10 sebelum menulis kode.
• Tanda soal DP: menanyakan paling banyak/paling sedikit/berapa cara, setiap langkah berupa pilihan, dan sisa soal hanya bergantung pada sedikit informasi.

Latihan bergaya OSN

Ketiga soal berikut mewakili tiga bentuk DP yang paling sering muncul: menghitung banyaknya cara pada grid, memilih dengan pantangan, dan memeriksa apakah sebuah jumlah bisa dibentuk.

Kerangka ketiganya ada di exercises/13/osn/.

Soal 1 — Jalur Grid Berhalangan

Sebuah denah berbentuk kotak-kotak berukuran R baris dan C kolom. Sebagian petaknya bisa dilewati, sebagian terhalang. Seekor semut berada di petak kiri atas dan ingin sampai ke petak kanan bawah. Dari sebuah petak, ia hanya boleh melangkah ke kanan atau ke bawah, dan tidak boleh menginjak petak yang terhalang.

Hitung ada berapa jalur berbeda yang bisa ditempuh.

Format masukan. Baris pertama berisi dua bilangan bulat R dan C. R baris berikutnya masing-masing berisi C karakter: . untuk petak yang bisa dilewati dan # untuk petak terhalang.

Format keluaran. Satu baris berisi banyaknya jalur. Kalau tidak ada jalur sama sekali, cetak 0.

Batasan. 1 ≤ R, C ≤ 17.

Contoh masukan

3 3
...
.#.
...

Contoh keluaran

2

Penjelasan. Tanpa halangan ada enam jalur. Petak tengah yang terhalang memutus empat di antaranya, menyisakan dua: menyusuri tepi atas lalu tepi kanan, atau tepi kiri lalu tepi bawah.

Kerangkanya: exercises/13/osn/01-jalur-grid.cpp

Soal 2 — Tanpa Bertetangga

Sepanjang satu sisi jalan berjajar N warung, dan warung ke-i menghasilkan keuntungan Aᵢ bila disewa. Pemiliknya melarang dua warung yang bersebelahan disewa oleh orang yang sama.

Tentukan total keuntungan terbesar yang bisa diperoleh dengan menyewa sekumpulan warung yang tidak ada dua yang bersebelahan. Boleh juga tidak menyewa sama sekali.

Format masukan. Baris pertama berisi bilangan bulat N. Baris kedua berisi N bilangan bulat A₁ A₂ … A_N.

Format keluaran. Satu baris berisi total keuntungan terbesar.

Batasan.

• 1 ≤ N ≤ 200.000
• 0 ≤ Aᵢ ≤ 10⁹

Contoh masukan

6
3 2 7 10 12 5

Contoh keluaran

22

Penjelasan. Pilihan terbaik adalah warung ke-1, ke-3, dan ke-5: 3 + 7 + 12 = 22. Pilihan 3 + 10 + 5 hanya menghasilkan 18, dan 10 + 12 tidak boleh karena kedua warungnya bersebelahan.

Kerangkanya: exercises/13/osn/02-tanpa-bertetangga.cpp

Soal 3 — Bagi Dua Sama Berat

Panitia punya N karung dengan berat yang diketahui, dan dua truk yang identik. Seluruh karung harus dimuat, dan panitia ingin kedua truk membawa berat yang sama persis. Karung tidak boleh dibelah.

Tentukan apakah pembagian seperti itu mungkin.

Format masukan. Baris pertama berisi bilangan bulat N. Baris kedua berisi N bilangan bulat, berat setiap karung.

Format keluaran. Satu baris berisi YA atau TIDAK.

Batasan.

• 1 ≤ N ≤ 100
• 1 ≤ berat ≤ 100

Contoh masukan

4
1 5 11 5

Contoh keluaran

YA

Penjelasan. Truk pertama memuat karung 1, 2, dan 4 dengan total 1 + 5 + 5 = 11; truk kedua memuat karung 3 yang beratnya 11. Untuk masukan 1 2 5, jawabannya TIDAK karena totalnya 8 tetapi tidak ada bagian yang berjumlah 4.

Kerangkanya: exercises/13/osn/03-bagi-dua.cpp

Bingung atau sudah selesai? Buka halaman pembahasan PR.