Dynamic Programming

Apa itu Dynamic Programming ? Dynamic Programming (biasa disingkat DP) adalah suatu teknik algoritma untuk memecahkan masalah dimana solusi optimal dari masalah tersebut dapat dipandang sebagai suatu deret keputusan.

Halaman ini akan berisi kumpulan soal-soal Dynamic Programming(beserta clue) dan akan terus diupdate setiap saya menemukan soal-soal Dynamic Programming yang menarik .

Mohon tambahkan di bagian komentar apabila kalian menemukan soal-soal Dynamic Programming yang juga menarik untuk dikerjakan ^_^.

2262 – Bracket

Misalkan f(a,b) adalah cost terbaik dari sub-string yang dimulai dari posisi a dan diakhiri dengan posisi b. Yang kita ingin cari adalah f(0,N-1) dimana N adalah panjang string.

f(a,b) = 0, jika a>=b
f(a,b) = maximum( option1, option2) jika a < b
option1 = maximum( f(a,i) + f(i+1,b) ) untuk i=a sampai i=b-1.
option2 = 2 + f(a+1,b-1), jika karakter pada posisi a adalah pasangan karakter pada posisi b (Contoh: ‘[' dengan ']‘ dan ‘(‘ dengan ‘)’ ).
option2 = 0, jika karakter pada posisi a bukan pasangan karakter pada posisi b.
Kompleksitas total adalah O(N^3).

bracket.jpg

1832 – Little Shop of Flowers

Misalkan f(a,b) adalah cost terbaik bila kita mulai dari bunch ke-a dan vase ke-b.
Yang kita ingin cari adalah f(0,0).
f(a,b) = 0, jika a==F
f(a,b) = max( f(a+1,c+1) + cost[a][c] ), dimana c dimulai dari b sampai V-(F-a).
F -> banyak bunch
V -> banyak vase
cost[i][j] -> cost bila kita menaruh bunch ke-i pada vase ke-j
Kompleksitas total adalah sekitar O(F^2 * V).