My first Magazine pemrograman-kompetitif-dasar | Page 89

7.2 Contoh-contoh DP Sederhana
kasus ini, urutan pengisian adalah
•
•
•
•
•
d p[1][1], d p[2][2], ..., d p[N][N],
lalu d p[1][2], d p[2][3], ..., d p[N − 1][N],
lalu d p[1][3], d p[2][4], ..., d p[N − 2][N],
lalu d p[1][4], d p[2][5], ..., d p[N − 3][N],
dan seterusnya sampai d p[1][N].
Ingat bahwa pengisian "tabel" harus dilakukan dari kasus yang kecil ke besar. Definisi "kasus
kecil" pada masalah ini adalah kayu dengan titik-titik pemotongan yang lebih sedikit. Dari contoh
ini kita mempelajari bahwa urutan pengisian "tabel" pada DP bottom-up tidak selalu biasa. Jika
urutan pengisiannya salah, maka hasil akhir yang didapatkan juga bisa jadi salah. Hal in terjadi
ketika kita hendak menyelesaikan kasus yang besar, tetapi hasil untuk kasus-kasus yang lebih
kecil belum tersedia. Untuk mengetahui urutan pengisian "tabel", Anda perlu mengamati apa
definisi "kasus kecil" pada masalah yang dihadapi.
79