Dan sekarang aku agak meloncat dikit ke bagian agak sedikit advanced, yaitu DP.
Dan jika ada kode, saya akan menuliskan dalam bahasa C++. (seharusnya kode untuk Pascal tidak akan jauh berbeda)

Level	Intermediate
Type	Dynamic Programming
Requirement	Recursive Function Multidimensional Array Big O Notation
Similar	Knapsack Zero One Matrix Chain Multiplication (MCM) Longest Increasing Subsequence (LIS) Coin Change Problem

Sekilas Tentang Dynamic Programming

Jadi seperti yang kita lihat, Dynamic Programming, dan namanya keren abis.
Padahal sebenarnya konsepnya tidak semenakutkan seperti namanya.

Dynamic Programming, yang nantinya disebut DP supaya singkat, itu memiliki dua tipe yaitu DP Top Down dan DP Bottom Up.

Apa bedanya? Nanti aku akan beri tahu bedanya.
Tetapi untuk sekarang, jika aku berbicara DP, itu aku mengacu kepada DP Top Down karena paling sering dan gampang dipakai.
Sedangkan DP Bottom Up itu biasanya dipakai kalau terpaksa gak bisa diselesaikan oleh DP Top Down, dan untuk bisa DP Bottom Up, menurut saya harus bisa dulu DP Top Down.

Nah pada dasarnya DP itu adalah sebuah fungsi rekursif.
Udah gitu doang dasarnya.
Kalau anda sudah mahir rekursif, seharusnya DP tidak akan sulit bagi anda.

Jadi kenapa kita diharuskan belajar DP?
Karena DP bisa mempercepat kompleksitas program kita.

Struktur DP

Ide DP itu sebenarnya simpel, misalkan anda ada fungsi rekursif yang memerlukan dua parameter a dan b, misalkan

int test(int a, int b)
{
  if(basecase)
  {
    // basecase
  } else
  {
    // rekurens
  }
}

Nah, jika kita diberikan memasukkan 3 dan 5, dan ntah bagaimana caranya dia akan mengembalikan 6, dan terus misalkan ntah dibagian program lain kita masukkan 3 dan 5 juga, maka dia akan mengembalikan 6 lagi. Artinya jika fungsi itu diberikan masukkan yang sama dan akan keluar hasilnya yang sama juga, maka fungsi tersebut bisa kita DP-in.

Seperti yang kita lihat, jika kita sudah tahu masukkan 3 dan 5 akan menghasilkan 6, kita jadi tidak perlu menghitung lagi, kita tinggal simpan hasil dari fungsi saat dia memproses 3 dan 5, kemudian jika diberikan input yang serupa, kita tinggal ambil dari simpanan kita.
Hal ini disebut dengan memoization. (Yup ini gak salah tulis, bukan memorization, tetapi memoization, diambil dari kata memo).
Cukup simpel bukan.

Dalam menyimpan data tersebut kita harus mempunyai array dengan jumlah state yang sama dengan jumlah parameter fungsi.
Dalam kasus diatas, kita memiliki dua parameter, sehingga kita perlu menyiapkan array 2D.

int test(int a, int b)
{
  if(memo[a][b] == -1)
  {
    if(basecase)
    {
      // basecase
    } else
    {
      // rekurens
    }
  }
  return memo[a][b];
}

Pertama - tama kita harus mengeset semua isi array tersebut dengan -1, sebagai penanda kalau state tersebut belum dihitung. Jika sudah dihitung dia akan skip bagian menghitungnya dan langsung ke mengembalikan nilai.
Nah hal tersebut boleh dilakukan jika anda bisa memastikan bahwa -1 tidak dihitung sebagai nilai. *misalnya anda yakin pasti hasil dari fungsi tersebut adalah bilangan positif

Kalau ternyata mau tidak mau -1 tersebut harus digunakan, maka, biasanya saya akan membuat satu array lagi tetapi tipe datanya boolean. Jadi sebagai penanda apakah itu sudah pernah dihitung atau belum.
Jadi kodenya seperti ini

int test(int a, int b)
{
  if(!vis[a][b])
  {
    if(basecase)
    {
      // basecase
    } else
    {
      // rekurens
    }
  }
  return memo[a][b];
}

Contoh Simpel DP

Nah sudah dapat gambaran kan? Untuk mempelajari DP tidak cukup hanya mengetahui teorinya aja... tapi dengan contoh bisa menjelaskan semuanya.

Contoh sederhananya adalah fungsi fibonacci.
Fungsi fibonacci biasanya didefinisikan seperti ini

f(n) = f(n-1) + f(n-2);
f(0) = 0;
f(1) = 1;

Nah jika kita buat rekursif sederhana, jadinya nanti begini

int fib(int n)
{
  int ret;
  if(n == 0) ret = 0;
  else if(n == 1) ret = 1;
  else ret = fib(n-1) + fib(n-2);
  return ret;
}

Gitu aja kan... simpel, tapi bagaimana dengan kompleksitasnya?
Untuk ngitung kompleksitas fibonacci rekursif seperti ini memang agak ribet, dan kompleksitas ini lebih besar daripada O(N).
Ya tau darimana yang penting ikutin aja, yang penting itu gede *LOL maksa.
Edited : tadi tahu dari kak Gozali kalau ini bisa dihitung secara kasar, karena tiap fungsi manggil dua fungsi lainnya, dan kedalaman yang paling dalam itu N, sehingga O(2*2*2*2*...*2), 2 nya ada sebanyak N kali jadi O(2^N). Walaupun sebenarnya gak pernah sampai 2^N, ya tapi namanya juga kasarannya :p.

Jika kita DP-in kompleksitasnya bisa nyurut jadi O(N).

int fib(int n)
{
  if(memo[n] == -1)
  {
    if(n == 0) memo[n] = 0;
    else if(n == 1) memo[n] = 1;
    else memo[n] = fib(n-1) + fib(n-2);
  }
  return memo[n];
}

Kelihatan tidak jauh berbeda kan?
Tapi ini kompleksitasnya O(N) dan jauh lebih mudah dihitung.
Jadi misalkan anggap semua pemanggilan rekursif didalam fungsi itu O(1), jadi untuk menghitung satu state kita perlu O(1) kan? Karena tidak ada rekursif. Kemudian worstcase kita, kita menghitung semua state. Karena statenya ada N, maka O(N).
Sehingga kita tinggal kalikan saja jadi O(N * 1) = O(N)

Kompleksitas DP

Pada dasarnya untuk menghitung kompleksitas DP caranya cukup mudah.

Kalikan semua statenya, kemudian hasilnya kalikan dengan kompleksitas di dalam fungsi itu dengan menganggap pemanggilan rekursif itu O(1).

Misalkan fungsi berikut

// a <= A
// b <= B
// c <= C
int function(int a, int b, int c)
{
  // O(B.log A)
}

Misalkan seperti diatas, kompleksitasnya adalah O(A.B.C * B.log A) = O(A.B^2.C.log A) Gampang kan ;).

Summarize

Secara umum, soal bisa di DP-in kalau punya hal ini

• jawaban dari soalnya itu bisa direpresentasikan dalam state
• mempunyai subproblem dan subsolution, maksudnya kira2 kalau tidak salah, dari suatu state, kita bisa tau nilainya tersebut dengan memproses state lain
• perpindahan statenya tidak siklis, maksudnya jika suatu state, sebut state A, memerlukan state B, dan state B memerlukan state C, tapi state C memerlukan state A, ini tidak bisa di DP *dan rasanya gak make sense juga
• ada problem overlapping (apa gitu istilahnya), yaitu misalkan state A memerlukan state B, sedangkan state C memerlukan state B juga, nah ini artinya overlapping, dari dua state yang berbeda, ujung2nya ada memanggil state yang sama. Kalau tidak ada, seharusnya kalau problemnya kita DP-in, kompleksitasnya tidak akan berubah, masih sama dengan cara rekursif biasa
• dan yang terakhir, setiap problem DP, pasti bisa direpresentasiin dengan rumus2, sederhananya ya kayak fibonaci tadi. Karena itu agak menyenangkan mengerjakan soal DP, jika sudah ketemu rumusnya, problemnya jadi gampang banget dikoding

Dan untuk introduction aku rasa cukup sekian... Misalnya kalian menemukan soal DP dan masih belum begitu mengerti, kalian bisa komen dibawah untuk dibahas nanti. Karena untuk mengerti DP harus ngerjain contoh - contoh gitu. Dan sekarang aku gak tau contoh apa yang cukup simpel yang bisa dimengerti untuk yang baru kenal.

Nanti di post terpisah aku akan memberikan contoh - contoh DP yang klasik, artinya DP nya sudah diberikan secara turun menurun dan menjadi basic problem DP, seperti knapsack, lis, mcm, dan sebagainya.