My first Magazine pemrograman-kompetitif-dasar | Page 84

7 Dynamic Programming
12:
13:
14:
15:
16:
best ← min(best, d p[i − 1][c − a[i]] + 1)
end if
d p[i][c] ← best
end for
end for
return d p[N][G]
18: end function
17:
7.2.3 Longest Common Subsequence
Contoh Soal 7.4: Longest Common Subsequence (LCS)
Diberikan 2 buah string A dan B. Panjang kedua string tidak harus sama. Berapa panjang
string terpanjang yang merupakan subsequence dari A dan B?
Subsequence dari sebuah string adalah string lain yang dapat dibentuk dengan menghapus
beberapa (boleh nol) karakter dari string asli tanpa mengubah urutannya. Sebagai contoh,
"gak", "oak", "gerak", dan "gerobak" adalah subsequence dari "gerobak", sementara "garuk",
"ombak", "gerebek", dan "georbak" bukan.
Contoh
A = "ajaib"
B = "badai"
LCS dari A dan B adalah "aai", dengan panjang 3.
Kita bisa definisikan d p(i, j) sebagai panjang subsequence terpanjang dari i karakter pertama
dari A dan j karakter pertama dari B. Jika karakter ke-i dari A, atau dinotasikan dengan A i sama
dengan B j , maka kita bisa memasangkan karakter tersebut sebagai kandidat subsequence . Jika
A i 6 = B j , maka A i tidak bisa dipasangkan dengan B j . Dalam kasus ini, kita perlu mengecek
subpersoalan untuk mencari LCS dari i karakter pertama pada A dan j − 1 karakter pertama
pada B, atau i − 1 karakter pertama pada A dan j karakter pertama pada B, lalu dipilih yang
menghasilkan LCS terpanjang. Dari sini kita juga bisa lihat bahwa jika i atau j adalah 0, maka
d p(i, j) = 0. Ini adalah base case dari persoalan LCS.
Dengan demikian d p(i, j) dapat dirumuskan sebagai berikut:

i = 0 ∨ j = 0
 0,
d p(i − 1, j − 1) + 1,
A i = B j
d p(i, j) =

max(d p(i − 1, j), d p(i, j − 1)),
A i 6 = B j
Analisis Kompleksitas
Jika panjang string A adalah M dan panjang string B adalah N, maka terdapat O(M) nilai
berbeda untuk nilai i dan O(N) nilai berbeda untuk nilai j pada d p(i, j). Dibutuhkan O(1) untuk
menghitung d p(i, j). Sehingga untuk menghitung seluruh nilai d p(i, j) untuk seluruh i dan j
dibutuhkan waktu O(NM).
74