Dynamic Programming

1. Fibonacci (coming soon!)

2. Koefisien Binomial
    C(n, k) = C(n-1, k-1) + C(n-1, k) dimana n > k > 0

3. Coin Change (coming soon or coming never.. idk)

4. Binary Search Tree yang optimal
cth:
A = 0,1
B = 0,2
C = 0,4
D = 0,3

Subproblem {1,2} -> dlm hal ini A=1, B=2, dst, nilai ini merupakan nilai k
A -> B
Cost: 1 * 0,1 + 2 * 0,2 = 0,3

B -> A
Cost: 1* 0,2 + 2 * 0,1 = 0,4

pilih yg cost terkecil, maka arah dari A -> B

Subproblem {3,4}
C -> D
Cost: 1 * 0,4 + 2 * 0,3 = 1,0

D -> C
Cost: 1 * 0,3 + 2 * 0,4 = 1,1

nilai k yang dimaksud diatas berguna untuk menentukan yang mana yang jadi root dari tree tersebut. misalkan k = 1, berarti rootnya adalah A
jadi susunannya: A -> B -> C -> D
(anggap ini dlm bentuk tree, penyusunan berdasarkan abjad. kalau abjad yang ingin dimasukkan ke tree lebih besar dari root nya (misal B adalah huruf yg lebih besar dari A, F adalah huruf yang lebih besar dari C, dsb) maka menjadi cabang tree di sebelah kanan root, dan sebaliknya jika lebih kecil maka menjadi cabang tree sebelah kiri.)

jadi dari aturan diatas, k = 2 dapat dituliskan sbb:
              B
           /      \
         A       C
                     \
                     D