Level	Intermediate
Type	Dynamic Programming
Requirement	Introduction to Dynamic Programming
Similar	Introduction to Dynamic Programming Knapsack Zero One Longest Increasing Subsequence (LIS) Coin Change Problem

Ketemu lagi... dengan saya alijaya, sekarang akan saya jelaskan tentang Matrix Chain Multiplication.

Penjelasan Matrix Chain Multiplication

Matrix Chain Multiplication biasanya diselesaikan dengan cara Dynamic Programming. Ini merupakan soal klasik Dynamic Programming juga. Jadi inti soalnya adalah, anda diberikan sejumlah matrix yang akan dikalikan secara berurutan. Suatu matrix akan berukuran P x Q dan matrix selanjutnya akan berukuran Q x R. Atau kalau bisa dibilang antara dua matrix yang bersampingan, jumlah kolom matrix pertama akan sama dengan jumlah baris matrix kedua. Dan didefinisikan dari cost untuk mengalikan antara matrix P x Q dan matrix Q x R adalah P x Q x R. Sebagai contoh matrix 5 x 7 dikali dengan matrix 7 x 3 mempunyai cost 5 x 7 x 3 = 63.

Perlu diketahui untuk perkalian matrix ini bersifat asosiatif, artinya jika ada urutan matrix A x B x C, maka perkalian (A x B) x C, akan mempunyai HASIL yang sama dengan A x (B x C). Tapi mereka mempunyai COST yang berbeda.

Misalkan matrix A berukuran 5 x 7, matrix B berukuran 7 x 3, dan matrix C berukuran 3 x 4.
Maka dengan cara (A x B) x C akan menghasilkan cost sebagai berikut.
Untuk (A x B) membutuhkan cost 5 x 7 x 3 =105 dan menghasilkan matrix berukuran 5 x 3.
Kemudian matrix tersebut dikalikan dengan matrix C membutuhkan cost 5 x 3 x 4 = 60.
Maka total cost keseluruhan adalah 105 + 60 = 165.

Sedangkan dengan cara A x (B x C) akan menghasilkan cost sebagai berikut.
Untuk (B x C) membutuhkan cost 7 x 3 x 4 = 84 dan menghasilkan matrix berukuran 7 x 4.
Kemudian matrix A dikalikan dengan matrix tersebut membutuhkan cost 5 x 7 x 4 = 140.
Sehingga total cost keseluruhan adalah 84 + 140 = 224.

Biasanya yang dicari adalah berapa jumlah cost minimal untuk mengalikan matrix tersebut. *bisa juga kalau problemnya aneh nanya cost maximalnya*.
Atau kalau nggak, apa konfigurasi kurung - kurungannya untuk menghasilkan cost minimal.

Analisis Problem

Ini soal bisa dengan susah diselesaikan dengan brute force, tetapi dengan mudah menggunakan Dynamic Programming. Ya kalau cara brute force artinya kita coba semua kemungkinan, sesimpel itu tapi ngodingnya ribet :p. Karena saya malas menjelaskan gimana ngebrute-forcenya, kita langsung lari ke Dynamic Programmingnya saja *plak*.

Dynamic Programming O(N^3)

Ok, pertama kok N^3? Kok gak efisien banget? ==a... Mohon jangan banyak protes, karena memang segitu adanya ._.
*Tadi baru liat di Wikipedia, katanya ada algo yang bisa sampe O(N log N)*

Ok... cukup sampai disitu... Kita mulai serius diskusinya.
Bentar, sebelum mulai aku mau kasih satu quote dulu "Inget DP, inget goyang gergaji rekursif" - by alijaya.
DP itu sebenernya gampang, yang susah itu nyari rekursifnya.

Jadi anggap kita punya dua matrix doang, cost minimalnya pasti cost nya mereka pas dikali kan?
Nah... misalkan kita ada urutan matrix misalkan A x B x C x D, nah kita bisa pecah urutan itu jadi 2 bagian, pilihannya adalah (A) x (B x C x D), atau (A x B) x (C x D), atau (A x B x C) x (D).
Bagian yang menariknya adalah, semua yang didalam kurung itu ntah bagaimana prosesnya pasti akan menjadi satu matrix kan? Jadi kalau kita pisahin dua, jadi kita punya dua matrix, dan cost minimalnya adalah kedua matrix itu dikaliin.
Seems simple right? But wait... MASALAHNYA kita mau pisahin kayak gimana supaya costnya minimal kan?
Karena itu kita harus cek satu - satu, kita liat mana yang minimal. Dan kabar baiknya, kita bisa ngerekursif problem yang ada di dalam kurung tersebut menggunakan metode yang sama. Misalkan dari problem A x B x C x D, kita niatnya misahin jadi (A) x (B x C x D), nah yang B x C x D kita bisa lakuin hal yang sama, jadi misahin antara (B) x (C x D) atau (B x C) x (D).

Jadi apa yang udah kita discover? Artinya fungsi rekursif kita akan perlu dua parameter untuk menandakan jangkauan mana yang kita ingin cari cost minimalnya.
Anggap aja fungsi itu f(l, r), artinya fungsi ini mengembalikan cost minimal untuk mengalikan matrix yang ada di antara l sampai r.
Dan untuk "ngebelah" dimana, kita harus ngeloop sebanyak dari l sampai r atau itungan kasarnya N kali. Karena itu ini algonya O(N^3), karena N^2 dari statenya, dan N dari loop di dalemnya.

f(l, r) = min{i in l...r}( f(l, i) + f(i+1, r) + m[l] * m[i+1] * m[r+1] );
f(x, x) = 0;

Dan muncul rumus yang aneh... aku gak tau konvensinya tapi aku tulis gitu, jadi aku cari minimal dari i diantara l <= i < r, maksudnya aku ngebelah di i, jadi cost minimal yang mungkin adalah cost minimal yang sebelah kiri yaitu f(l, i) ditambah cost minimal yang disebelah kanan yaitu f(i+1, r) ditambah cost untuk ngaliin dua matrix yang baru itu, yaitu m[l] * m[i+1] * m[r+1]. Dimana m adalah array yang berisi size dari matrix. Karena jumlah kolom matrix pertama sama dengan jumlah baris matrix kedua, jadi itu cukup aku simpan sekali aja. Contoh kasus di atas yang matrix A berukuran 5 x 7, matrix B 7 x 3, dan matrix C 3 x 4 akan aku simpan di matrix m sebagai berikut [5, 7, 3, 4]. Jadi untuk mengetahui jumlah baris suatu matrix adalah m[x], kalau kolom m[x+1]. Terus yang f(x, x) = 0 itu kalau l dan r nya sama, artinya cuman satu elemen, jadi pastinya 0 costnya. Dan kodingnya tinggal merem aja LOL XD.

int f(int l, int r)
{
  int& hasil = memo[l][r];
  if(hasil == -1)
  {
    if(l == r)
    {
      hasil = 0;
    } else
    {
      hasil = inf;
      for(int i=l; i<r; i++) hasil = min(hasil, f(l, i) + f(i+1, r) + m[l] * m[i+1] * m[r+1]);
    }
  }
  return hasil;
}

Selesai~...
Gitu aja?
Yups...
Ciyus?
Cuer Dah~...

That's it...
Ciao~...