13. Dynamic programming — Pembahasan PR

Berkas .cpp jawabannya ada di exercises/13/homework/solutions/.

Halaman ini dibuka sesudah mencoba sendiri. Bandingkan jalan pikiranmu dengan bagian Cara berpikir, bukan kodenya baris per baris: dua kode yang berbeda bentuk bisa sama-sama benar, dan yang perlu ditiru adalah cara sampai ke sana. Bagian Uji di tiap soal berisi masukan dan keluaran yang sudah diperiksa — jalankan jawabanmu sendiri dengan masukan itu sebelum merasa selesai.

Menjalankan salah satu jawabannya:

g++ -std=c++17 -O2 -o jawab exercises/13/homework/solutions/01-tangga.cpp
./jawab

Soal 1 — Naik tangga bertiga

Soal. Banyaknya cara mencapai anak tangga ke-n dengan langkah 1, 2, atau 3.

Cara berpikir. Lima langkah:

1. Keadaan. dp[i] = banyaknya cara mencapai anak tangga ke-i.
2. Kasus dasar. dp[0] = 1, dp[1] = 1, dp[2] = 2 (yaitu 1+1 dan 2).
3. Transisi. dp[i] = dp[i-1] + dp[i-2] + dp[i-3].
4. Urutan. Dari kecil ke besar.
5. Jawaban. dp[n].

Kasus dasar harus tiga buah, bukan dua: transisi untuk i = 2 akan menyentuh dp[-1] kalau dipaksakan.

Pembahasan.

dp[0] = 1;
if (n >= 1) dp[1] = 1;
if (n >= 2) dp[2] = 2;

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

cout << dp[n] << "\n";

Untuk n = 5 jawabannya 13.

Uji.

Baris terakhir sekaligus menguji dua hal: arraynya cukup besar untuk n = 10⁶, dan % MOD diambil di setiap penjumlahan, bukan hanya di akhir.

Kesalahan umum.

• Menulis if (n >= 2) dp[2] = 2; tanpa penjaga n >= 1 dan n >= 2, lalu membaca dp[n] yang berisi sampah untuk n kecil.
• Lupa % MOD di dalam perulangan, sehingga meluap walaupun jawabannya akhirnya di-modulo.
• Memakai int untuk dp. Penjumlahan tiga nilai hampir 10⁹ melewati batas int sebelum sempat di-modulo.

Soal 2 — Koin paling sedikit

Soal. Koin paling sedikit untuk mencapai k, atau -1.

Cara berpikir. Keadaannya dp[v] = koin paling sedikit untuk nilai v. Nilai awal BESAR berarti "belum/tidak bisa dicapai". Transisinya mencoba setiap koin sebagai koin terakhir yang diambil.

Kenapa memeriksa semua koin, bukan mengambil yang terbesar? Karena inilah soal yang membuat greedy gagal di Bab 12. DP mencoba semuanya, dan karena setiap nilai dihitung sekali, biayanya tetap murah.

Pembahasan.

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";

Periksa: koin 1 3 4 dengan k = 6 memberi 2; koin 2 4 dengan k = 7 memberi -1 karena semua koin genap.

Uji.

Dua baris terakhir menguji jalur "tidak mungkin". Yang membedakan jawaban benar dan salah di sini adalah nilai penanda BESAR: ia harus cukup besar untuk tidak pernah menang saat dibandingkan, tetapi dp[v - c[i]] + 1 tidak boleh meluap karenanya.

Kesalahan umum.

• Memakai BESAR yang terlalu besar sehingga dp[v - c[i]] + 1 meluap. Satu miliar aman untuk int; 2147483647 tidak.
• Mencetak dp[k] tanpa memeriksa apakah nilainya masih BESAR.

Soal 3 — Banyaknya cara

Soal. Cacah cara membentuk k, urutan tidak dibedakan.

Cara berpikir. Inilah satu-satunya soal DP di bab ini yang jawabannya bergantung pada urutan dua perulangan:

• koin di luar, nilai di dalam → mencacah kombinasi (1+3 sama dengan 3+1),
• nilai di luar, koin di dalam → mencacah urutan (1+3 berbeda dari 3+1).

Soal ini meminta yang pertama. Bayangkan setiap koin ditawarkan sekali kepada seluruh nilai: karena koin 3 baru ditawarkan setelah koin 1 selesai, susunan yang memakai koin 1 sesudah koin 3 tidak pernah terbentuk.

Kasus dasarnya dp[0] = 1: ada tepat satu cara membentuk nilai nol, yaitu tidak mengambil apa pun.

Pembahasan.

dp[0] = 1;
for (int i = 0; i < m; i++)
    for (int v = c[i]; v <= k; v++)
        dp[v] = (dp[v] + dp[v - c[i]]) % MOD;

cout << dp[k] << "\n";

Untuk koin 1 3 4 dan k = 6 jawabannya 4: 1+1+1+1+1+1, 1+1+1+3, 3+3, 1+1+4.

Uji.

Kasus pertama adalah pemeriksaan bahwa urutan tidak dianggap berbeda: 3 + 3 dan 1 + 1 + 4 dihitung masing-masing sekali. Kalau jawabanmu jauh lebih besar, kemungkinan besar urutan perulangannya terbalik — koin di dalam, nilai di luar — yang menghitung 1 + 3 dan 3 + 1 sebagai dua cara berbeda.

Kesalahan umum.

• Menukar urutan perulangan, lalu mendapat 9 alih-alih 4.
• Menulis dp[0] = 0, sehingga seluruh jawaban menjadi nol.

Soal 4 — Knapsack 0/1

Soal. Nilai terbesar dengan batas berat W.

Cara berpikir. Keadaan dua dimensi: dp[i][b] = nilai terbesar memakai i barang pertama dengan batas berat b. Untuk setiap barang hanya ada dua pilihan — ambil atau tidak — dan DP mencoba keduanya.

Kata kunci "setiap barang paling banyak sekali" itulah yang membuat baris i hanya boleh melihat baris i − 1. Kalau ia melihat barisnya sendiri, barang yang sama bisa terambil berkali-kali (dan itu justru rumus untuk soal koin yang boleh diulang).

Pembahasan.

for (int i = 1; i <= n; i++) {
    for (int b = 0; b <= W; b++) {
        dp[i][b] = dp[i - 1][b];
        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];
    }
}
cout << dp[n][W] << "\n";

Pada contoh berkas PR, greedy menurut nilai per berat menjawab 10 sedangkan DP menjawab 14 — satu barang "efisien" seberat 6 kalah oleh dua barang seberat 5.

Uji.

Kasus kedua sama dengan tabel penelusuran di Bab 13, jadi kamu bisa membandingkan isi dp milikmu sel demi sel kalau jawabannya meleset. Kasus pertama menguji cabang "tidak diambil": jawabannya 0, bukan nilai barangnya.

Kesalahan umum.

• Menyimpan data mulai dari indeks 0 tetapi menulis transisi dengan dp[i-1], sehingga barang pertama terlewat. Pilih satu gaya penomoran dan konsisten.
• Membuat array dp[105][10005] sebagai variabel lokal di dalam main. Ukurannya sekitar 4 MB — terlalu besar untuk memori tumpukan. Letakkan sebagai variabel global.

Tantangan — Barisan naik terpanjang

Soal. Panjang barisan naik terpanjang, n ≤ 5.000.

Cara berpikir. Keadaan yang tepat adalah dp[i] = panjang barisan naik terpanjang yang berakhir tepat di elemen ke-i. Kata "berakhir tepat di" itu penting: tanpa itu, transisinya tidak bisa ditulis, karena kita perlu tahu nilai elemen terakhir untuk memutuskan apakah elemen berikutnya boleh disambung.

Transisinya: lihat semua j < i; kalau a[j] < a[i], barisan yang berakhir di j boleh dilanjutkan ke i.

Jawabannya bukan dp[n-1], melainkan nilai terbesar di seluruh dp — karena barisan terpanjang belum tentu berakhir di elemen terakhir.

Jumlah langkahnya O(n²) = 25 juta untuk n = 5.000. Masuk. (Ada cara O(n log n) yang dipakai di soal berbatasan lebih besar, tetapi itu di luar cakupan buku ini.)

Pembahasan.

int terpanjang = 0;
for (int i = 0; i < n; i++) {
    dp[i] = 1;
    for (int j = 0; j < i; j++)
        if (a[j] < a[i] && dp[j] + 1 > dp[i]) dp[i] = dp[j] + 1;
    if (dp[i] > terpanjang) terpanjang = dp[i];
}
cout << terpanjang << "\n";

Untuk 3 1 4 1 5 9 2 6 jawabannya 4.

Uji.

Baris ketiga adalah kasus tepi yang paling sering salah: nilai yang sama tidak boleh dianggap naik. Kalau syaratnya ditulis a[j] <= a[i], jawabannya menjadi 6 dan seluruh subsoal dengan data berulang ikut salah.

Kesalahan umum.

• Mencetak dp[n-1]. Untuk 1 2 3 0 jawabannya 3, tetapi dp[3] = 1.
• Memakai a[j] <= a[i], yang mengizinkan nilai sama dan mengubah soal menjadi "tidak menurun".
• Lupa dp[i] = 1 sebagai nilai awal, sehingga elemen yang tidak bisa disambung berakhir bernilai nol.

Latihan bergaya OSN — pembahasan

Berkas jawabannya ada di exercises/13/osn/solutions/.

Soal 1 — Jalur Grid Berhalangan

Keadaannya. dp[i][j] adalah banyaknya jalur dari petak kiri atas sampai petak (i, j).

Cara berpikir. Sebuah petak hanya bisa dimasuki dari atas atau dari kiri, dan kedua jalan itu tidak pernah menghasilkan jalur yang sama. Jadi dp[i][j] = dp[i-1][j] + dp[i][j-1]. Petak terhalang bernilai 0, karena tidak ada jalur yang boleh berakhir di situ. Petak awal bernilai 1 — itu "jalur kosong" yang belum melangkah ke mana-mana.

Perhatikan urutan pemeriksaannya di dalam kode: halangan diperiksa lebih dulu, baru petak awal. Kalau petak awal sendiri terhalang, jawabannya 0, dan urutan ini menanganinya tanpa cabang tambahan.

Karena setiap petak dihitung dari petak di atas dan di kirinya, perulangan harus berjalan dari baris atas ke bawah dan dari kolom kiri ke kanan.

Besarnya jawaban. Pada denah 17 × 17 tanpa halangan, jumlah jalurnya 601.080.390. Masih muat di int, tetapi tipis; long long menghilangkan keraguan.

Pembahasan.

vector<vector<long long>> dp(r, vector<long long>(c, 0));

for (int i = 0; i < r; i++) {
    for (int j = 0; j < c; j++) {
        if (peta[i][j] == '#') { dp[i][j] = 0; continue; }
        if (i == 0 && j == 0)  { dp[i][j] = 1; continue; }

        long long total = 0;
        if (i > 0) total += dp[i - 1][j];
        if (j > 0) total += dp[i][j - 1];
        dp[i][j] = total;
    }
}

cout << dp[r - 1][c - 1] << "\n";

Uji.

Kesalahan umum.

• Menetapkan dp[0][j] = 1 untuk seluruh baris pertama tanpa memeriksa halangan. Satu halangan di baris pertama seharusnya memutus seluruh sisa baris itu.
• Membaca peta dengan getline setelah cin >> r >> c tanpa membersihkan sisa baris, sehingga baris pertama peta terbaca kosong. Memakai cin >> peta[i] menghindari masalah ini seluruhnya.
• Menjalankan perulangan dari kanan ke kiri, sehingga dp[i][j-1] dibaca sebelum diisi.

Soal 2 — Tanpa Bertetangga

Keadaannya. dp[i] adalah keuntungan terbesar yang bisa diperoleh dari i warung pertama.

Cara berpikir. Untuk warung ke-i hanya ada dua kemungkinan, dan keduanya sudah mencakup semua kasus:

• warung itu tidak disewa, sehingga hasilnya sama dengan dp[i-1];
• warung itu disewa, sehingga tetangganya tidak boleh, dan hasilnya dp[i-2] + A[i].

Ambil yang lebih besar. Keadaan awalnya dp[0] = 0 (tidak ada warung) dan dp[1] = A[1].

Menghemat memori. Rumusnya hanya menyentuh dua nilai terakhir, jadi seluruh array tidak perlu disimpan — cukup dua variabel yang bergeser. Untuk N = 200.000 array long long memakan 1,6 MB, yang sebenarnya masih aman; tetapi kebiasaan ini menjadi penting saat tabelnya dua dimensi.

Pembahasan.

long long duaLalu = 0, satuLalu = 0;
for (int i = 0; i < n; i++) {
    long long x;
    cin >> x;

    long long sekarang = satuLalu;
    if (duaLalu + x > sekarang) sekarang = duaLalu + x;

    duaLalu = satuLalu;
    satuLalu = sekarang;
}

cout << satuLalu << "\n";

Urutan tiga baris terakhir penting: duaLalu harus menerima nilai satuLalu yang lama, bukan yang baru.

Uji.

Kesalahan umum.

• Mengambil warung berselang-seling secara greedy — ganjil semua atau genap semua. Untuk 3 2 7 10 12 5 cara itu menghasilkan 22 dan 17, jadi kebetulan benar; untuk 2 1 1 2 cara itu menghasilkan 3, padahal jawabannya 4.
• Memakai int untuk total: paling banyak 10⁵ warung yang tidak bersebelahan bisa disewa, jadi totalnya bisa mencapai 10⁵ × 10⁹ = 10¹⁴.
• Lupa bahwa jawabannya bisa berasal dari tidak menyewa apa pun, sehingga nilai awal diisi dengan angka negatif.

Soal 3 — Bagi Dua Sama Berat

Keadaannya. bisa[s] bernilai benar kalau jumlah berat tepat s bisa dibentuk dari karung-karung yang sudah diproses.

Cara berpikir. Dua truk berbobot sama berarti masing-masing membawa setengah dari total. Kalau totalnya ganjil, jawabannya langsung TIDAK — pemeriksaan satu baris yang menghemat seluruh perhitungan.

Kalau genap, pertanyaannya menjadi: adakah sekumpulan karung yang berjumlah tepat total / 2? Ini soal subset sum, dan penyelesaiannya adalah tabel boolean sepanjang total / 2 + 1. Mula-mula hanya jumlah 0 yang bisa dibentuk. Setiap karung baru menambah kemungkinan: kalau s − w sudah bisa dibentuk, maka s juga bisa.

Kenapa perulangan jumlahnya mundur. Kalau s berjalan naik, nilai bisa[s - w] yang dibaca mungkin baru saja diisi oleh karung yang sama pada putaran ini, sehingga satu karung terpakai dua kali. Berjalan mundur menjamin bisa[s - w] masih berisi keadaan sebelum karung ini diproses. Ini perbedaan antara "setiap barang sekali" dan "barang boleh diulang" yang disebut di bagian Tips.

Besarnya tabel. Total paling besar 100 × 100 = 10.000, jadi tabelnya paling panjang 5.001 dan seluruh perhitungannya 100 × 5.000 = 5 × 10⁵ langkah.

Pembahasan.

if (total % 2 != 0) { cout << "TIDAK\n"; return 0; }

int separuh = total / 2;
vector<bool> bisa(separuh + 1, false);
bisa[0] = true;

for (int i = 0; i < n; i++) {
    for (int s = separuh; s >= w[i]; s--) {
        if (bisa[s - w[i]]) bisa[s] = true;
    }
}

cout << (bisa[separuh] ? "YA\n" : "TIDAK\n");

Uji.

Kasus kedua penting: totalnya 8, jadi pemeriksaan ganjil-genap tidak menolongnya. Jawabannya harus datang dari tabelnya.

Kesalahan umum.

• Menjalankan perulangan jumlah dari kecil ke besar, sehingga satu karung bisa dipakai berkali-kali dan 1 2 5 dijawab YA.
• Lupa bisa[0] = true, sehingga seluruh tabel tetap salah.
• Mengira total genap sudah cukup sebagai jawaban.

Kalau masih tersendat

• Tidak tahu apa keadaannya → Bab 13, langkah 1 dari lima langkah. Tulis dp[i] sebagai kalimat lengkap sebelum menulis kode.
• Jawaban meleset sedikit → periksa kasus dasarnya; dp[0] = 0 dan dp[0] = 1 adalah dua soal yang berbeda.
• Tidak yakin soal ini DP atau bukan → Bab 13, bagian Mengenali soal DP.

Kalau sebuah keadaan sudah bisa ditulis sebagai kalimat, sisanya biasanya mengikuti. Kalau belum bisa, menulis kode hanya akan memperpanjang kebingungan.