Kerangka penyelesaian soal DP

Soal DP yang belum pernah dikerjakan menuntut keputusan desain, bukan hafalan rumus, dan keputusan itu bisa dirapikan menjadi kerangka empat langkah yang tetap. Kerangka ini berlaku untuk DP satu dimensi maupun dua dimensi, dan topik ini menerapkannya utuh dari nol pada satu soal baru, yaitu longest increasing subsequence, sambil memeriksa kompleksitas waktunya.

Mengenali soal DP#

Langkah pertama adalah berhenti sejenak dan memastikan soalnya memang layak dikerjakan dengan DP. Ada tanda-tanda yang cukup andal. Pertanyaannya berbentuk optimum, seperti nilai minimum atau maksimum, atau menghitung banyak cara. Keputusan diambil bertahap mengikuti deret masukan, sehingga posisi sekarang merangkum seluruh kemajuan yang lalu. Pilihan pada langkah sekarang membatasi pilihan langkah berikutnya, tetapi batasan itu bisa diringkas menjadi beberapa angka saja, seperti sisa kapasitas atau posisi terakhir. Terakhir, pencarian lengkap akan eksponensial, padahal jumlah ringkasan keadaannya jauh lebih kecil.

Kontrasnya juga penting. Bila satu kriteria serakah sudah terbukti optimal, greedy lebih murah daripada DP, seperti pada pemilihan kegiatan. Bila submasalahnya tidak tumpang-tindih, misalnya merge sort yang membelah masukan menjadi dua bagian yang terpisah, divide and conquer tanpa tabel sudah cukup. DP menempati tengahnya, yaitu soal rekursif yang cabang-cabangnya bertemu lagi di submasalah yang sama. Latihan termudahnya adalah membaca pertanyaan soalnya lebih dulu, baru memeriksa batasan masukannya, karena jenis pertanyaan lebih menentukan alat daripada ukuran masukan.

Empat langkah dari state ke jawaban#

Kerangka ini terdiri atas state, transisi, basis, dan urutan pengisian, dan keempatnya dikerjakan di kertas sebelum kode ditulis.

1. State. Nyatakan arti dp dalam satu kalimat tegas, misalnya dp[i] menyimpan X untuk prefiks sepanjang i. Kalimat ini adalah kontrak seluruh solusi, dan kegagalan di sini merembet ke semuanya.
2. Transisi. Hubungkan setiap sel dengan sel-sel yang lebih kecil, biasanya berbentuk maksimum, minimum, atau penjumlahan kandidat.
3. Basis. Tentukan sel terkecil yang jawabannya pasti tanpa transisi, seperti prefiks kosong atau satu elemen.
4. Urutan pengisian. Pilih arah pengisian yang menjamin setiap sel yang dirujuk transisi sudah selesai, lalu tetapkan dari sel mana jawaban akhir dibaca.

Langkah keempat sering diremehkan padahal menjadi tempat error paling senyap. Jawaban akhirnya juga perlu diperjelas, karena tidak selalu berada pada sel yang indeksnya sama dengan ukuran masukan. Pada state berbasis prefiks, jawabannya sel terakhir, sedangkan pada state berjangkar posisi, jawabannya maksimum di seluruh tabel. Pembedaan inilah yang akan terlihat jelas pada soal di bawah.

Menerapkan kerangka pada soal baru#

Soalnya, dari deret angka, cari panjang subderet yang naik ketat dan paling panjang, dan angka mana pun boleh dilompati, yaitu longest increasing subsequence (LIS). Deret contohnya [10, 9, 2, 5, 3, 7, 101, 18] dan jawabannya 4. Empat langkah kerangkanya dikerjakan berurutan.

1. State. dp[i] menyimpan panjang subderet naik terpanjang yang berakhir tepat pada indeks i. Kata berakhir tepat adalah jangkarnya, karena tanpa jangkar, transisi tidak tahu angka terakhir mana yang harus dibandingkan.
2. Transisi. Angka ke-i dapat menyambung dari angka mana pun di posisi sebelumnya yang nilainya lebih kecil:
   $$dp[i] = 1 + \max \{\, dp[j] \mid j < i,\ deret[j] < deret[i] \,\}$$
3. Basis. Setiap dp[i] bernilai minimal 1, karena satu angka sendirian sudah menjadi subderet naik sepanjang 1.
4. Urutan pengisian. Kiri ke kanan, karena setiap sel membaca sel-sel sebelumnya, dan jawaban akhirnya maksimum seluruh tabel, bukan sel terakhir.

"""Kerangka empat langkah diterapkan pada longest increasing subsequence."""

deret = [10, 9, 2, 5, 3, 7, 101, 18]

def lis(deret):
    n = len(deret)
    dp = [1] * n                     # basis: setiap angka sendirian panjangnya 1
    asal = [-1] * n
    for i in range(1, n):            # urutan pengisian: kiri ke kanan
        for j in range(i):
            if deret[j] < deret[i] and dp[j] + 1 > dp[i]:
                dp[i] = dp[j] + 1
                asal[i] = j
    return dp, asal

dp, asal = lis(deret)
print("deret:", deret)
print("dp   :", dp)
print("LIS  :", max(dp))

i = dp.index(max(dp))
sub = []
while i != -1:
    sub.append(deret[i])
    i = asal[i]
print("salah satu LIS:", list(reversed(sub)))

deret: [10, 9, 2, 5, 3, 7, 101, 18]
dp   : [1, 1, 1, 2, 2, 3, 4, 4]
LIS  : 4
salah satu LIS: [2, 5, 7, 101]

Tabelnya membenarkan keempat langkah itu. Sel untuk angka 7 bernilai 3 karena menyambung dari angka 5, sedangkan angka 101 dan 18 sama-sama bernilai 4 tanpa saling menyambung. Karena statenya berjangkar posisi, jawabannya max(dp), dan array asal menelusuri mundur menjadi subderet 2, 5, 7, 101. Perhatikan pula bahwa memaksa jawaban berada di dp[n-1] kebetulan menghasilkan 4 pada contoh ini, tetapi salah untuk deret lain, dan kekeliruan semacam ini baru terlihat pada kasus uji yang kecil.

Memeriksa kompleksitas#

Kompleksitas DP dihitung dari bentuknya sendiri, yaitu banyak state dikali biaya transisi per state, bukan dari stopwatch. Pada LIS, statenya n sel dan transisinya memindai paling banyak n kandidat, sehingga waktunya $O(n^2)$ dengan ruang $O(n)$ untuk tabel dan array asal. Pada lintasan kisi, statenya $m \times n$ sel dengan transisi tetap, sehingga $O(mn)$. Pada knapsack 0/1, statenya $n \times c$ sel sehingga $O(nc)$, dan angka c inilah yang menjelaskan mengapa kapasitas besar membuat tabelnya membengkak.

Angka-angka itu juga menjadi alat penilaian sebelum mengetik. Bila hasil kalinya terlalu besar untuk batas soal, cari cara meringkas state atau mempercepat transisi dengan struktur data, misalnya pencarian biner yang menurunkan LIS menjadi $O(n \log n)$. Bila state terlalu tipis untuk menangkap batasan soal, tambah satu dimensi, dan terima biayanya. Pemeriksaan dua arah ini menentukan apakah desain state layak dilanjutkan.

Varian Java#

Versi Java mengulang langkah yang sama tanpa perubahan logika. Basisnya ditulis sebagai perulangan yang mengisi setiap sel dengan satu, transisinya dua perulangan bersarang, dan jawabannya maksimum yang dipindai setelah tabel selesai.

import java.util.Arrays;

public class KerangkaDp {
    // LIS dengan kerangka empat langkah: state, transisi, basis, urutan pengisian

    static int[] lis(int[] deret) {
        int n = deret.length;
        int[] dp = new int[n];
        for (int i = 0; i < n; i++) {
            dp[i] = 1;                       // basis: satu angka panjangnya 1
        }
        for (int i = 1; i < n; i++) {        // urutan pengisian: kiri ke kanan
            for (int j = 0; j < i; j++) {
                if (deret[j] < deret[i] && dp[j] + 1 > dp[i]) {
                    dp[i] = dp[j] + 1;
                }
            }
        }
        return dp;
    }

    public static void main(String[] args) {
        int[] deret = {10, 9, 2, 5, 3, 7, 101, 18};
        int[] dp = lis(deret);
        int maks = 0;
        for (int v : dp) {
            maks = Math.max(maks, v);
        }
        System.out.println("deret: " + Arrays.toString(deret));
        System.out.println("dp   : " + Arrays.toString(dp));
        System.out.println("LIS  : " + maks);
    }
}

deret: [10, 9, 2, 5, 3, 7, 101, 18]
dp   : [1, 1, 1, 2, 2, 3, 4, 4]
LIS  : 4

Keluarannya identik dengan versi Python, termasuk isi tabel [1, 1, 1, 2, 2, 3, 4, 4]. Basisnya ditulis sebagai perulangan yang mengisi satu sel demi satu sel, bukan mengandalkan nilai bawaan, karena menuliskannya eksplisit membuat kontrak state-nya terbaca di kode. Pemindaian maksimum dilakukan setelah tabel selesai, sebagaimana ditegaskan langkah keempat, dan Arrays.toString mencetak tabel penuh agar perbandingannya dengan keluaran Python mudah dilakukan. Biayanya tetap $O(n^2)$ waktu dengan ruang $O(n)$, persis seperti perhitungan pada bagian kompleksitas, dan tidak ada rekursi yang menumpuk frame. Bila subderetnya juga perlu direkonstruksi, array asal pada versi Python cukup disalin sebagai array kedua. Struktur kode Java ini sekaligus menjadi ceklis keempat langkah kerangkanya, dari basis, transisi, urutan, sampai pembacaan jawaban.

Kesalahan umum#

1. Membaca jawaban dari sel terakhir padahal statenya berjangkar posisi. Pada LIS, sel terakhir hanya melaporkan subderet yang berakhir di situ. Perbaikannya memindai maksimum seluruh tabel, atau memilih state prefiks bila jawaban di ujung memang diinginkan.
2. State tanpa jangkar. dp[i] yang berarti LIS di prefiks i tidak cukup untuk transisi, karena angka terakhir subderetnya tidak diketahui. Perketat arti statenya menjadi berakhir tepat di i, atau tambahkan dimensi untuk menyimpan batasan yang hilang.
3. Basis yang terlupa membuat nilai bawaan menular. Tabel yang diisi 0 bawaan bahasa bisa berarti nol cara padahal maksudnya satu, dan seluruh transisi mewarisinya. Tetapkan basis secara eksplisit sebelum perulangan dimulai.
4. Urutan pengisian yang membaca sel yang belum selesai. Gejalanya angka yang tampak masuk akal tetapi lebih kecil dari jawaban seharusnya. Telusuri sel-sel yang dirujuk transisi dan pastikan semuanya terisi lebih dulu pada arah yang dipilih.

Ringkasan#

• Soal DP dikenali dari pertanyaan optimum atau banyak cara, keputusan bertahap, dan ringkasan keadaan yang jauh lebih kecil daripada pencarian lengkap.
• Kerangkanya empat langkah, yaitu state yang dinyatakan tegas, transisi antar sel, basis yang pasti, dan urutan pengisian yang menghormati ketergantungan.
• LIS dikerjakan utuh dengan state berjangkar berakhir di i, transisi maksimum dari kandidat yang lebih kecil, dan jawaban maksimum seluruh tabel.
• Kompleksitasnya dihitung sebagai banyak state kali biaya transisi, yaitu $O(n^2)$ untuk LIS dan $O(nc)$ untuk knapsack 0/1.

Referensi#

• Longest increasing subsequence — Wikipedia — rumusan LIS, solusi $O(n^2)$ dengan tabel dp, dan perbaikan $O(n \log n)$.
• Class Arrays — Java SE 21 & JDK 21 — Oracle — dokumentasi Arrays.toString yang dipakai untuk mencetak tabel pada varian Java.