• Suppose we have Coin 5, 6, 10
• What is the minimum of coin that gives the value of 12
• ถ้าที่เคยเรียนไปแล้ว
  • Brute Force ก็เอาทุก possible ways เลย แม้ว่า $5*1*1*1*1*1*1*1$
  • Greedy คือเราเลือกจากอันสูงสุดก่อน ก็คือ 10, ไล่ลงมา ก็เป็น $10*1*1$ (OK Solution)
    • แต่มันก็ไม่ได้ Optimal (เพราะเราใช่ 3 coin) แต่จริง ๆ มันก็มี $6*6$
    • Dynamic Programming ก็สามารถมาช่วยตรงนี้ได้!

Idea of Dynamic Programming

• Invented by Richard Bellman in the 1950s for optimizing multistage decision problems.
• "Programming" refers to planning, not coding.
• Used for problems with overlapping subproblems and optimal substructure.
  • Good for optimization problems
• Dynamic programming suggests solving each of the smaller subproblems only once and recording the results in a table from which we can then obtain a solution to the original problem.

Steps in Dynamic Programming

1. Characterize the structure of an optimal solution.
2. Define the value of an optimal solution recursively.
3. Compute the value iteratively (bottom-up fashion).
4. Construct the optimal solution (from computed information).

Fibonacci Example

Recursive (Inefficient)

ALGORITHM F(n)
BEGIN
    if n <= 1 then return n
    else return F(n-1) + F(n-2)
END.

This creates a large recursion tree with repeated calculations.

Tree of recursive calls for computing F(5)

• ถ้าดูอันนี้จะเห็นว่า F(2) ถูกเรียกตั้งหลายครั้ง มันก็จะ Compute ใหม่ทุกรอบเลย
• จริง ๆ เราสามารถใช้ Result จากการ Compute F(2) รอบเดียวเลยไม่ได้รึ?!

This is $O(2^n)$

Memoization (Top-Down)

ALGORITHM FibMemo(n)
BEGIN
    for i=0 to n do F[i] = -1
    return FibLookUp(n)
END.
 
ALGORITHM FibLookUp(n)
BEGIN
    if n < 2 then return n
    if F[n] = -1 then F[n] = FibLookUp(n-1) + FibLookUp(n-2)
    return F[n]
END.

Bottom-Up Approach (Efficient)

ALGORITHM FibDynamic(n)
BEGIN
    F[0] = 0;
    F[1] = 1;
    for i = 2 to n do
        F[i] = F[i-1] + F[i-2]
    return F[n]
END.

Alternatively, using O(1) space: (ข้างบนใช้ Array, ข้างล่างใช้ 2 Variable)

ALGORITHM FibDynamic2(n)
BEGIN
    fn1 = 0;
    fn2 = 1;
    for i = 2 to n do
        fn = fn1 + fn2;
        fn1 = fn2;
        fn2 = fn;
    return fn
END.

Coin Change Problem

• Given coins of denominations $d_1, d_2, ..., d_n$, find the minimum number of coins to make an amount $N$.
• Define $C[i,j]$ as the minimum number of coins needed to make $j$ using the first $i$ denominations.
• For example, the given coin denominations are $d_1=1,d_2=4,d_3=6$
  • Thus, $C[2,200]$ แปลว่าจะหา Minimum numberof coins to make change for the amount 200 baht, USING coins $d_1$ and $d_2$
  • เข้าใจมั้ยถ้าเป็น $C[3,200]$ ก็คือใช้ทุก Coin ไง

• Recurrence relation: $$C[i,j] = \min\{C[i-1,j], 1 + C[i,j-d_i]\}$$
  • ลองใช้สมการ สมมติมอง $4,$d_2$
    • $C[2,4]=\text{min}\{C[1,4],1+C[2,4-4]\}$
    • จะได้ความหมายว่า no user $4 coin, use one$1 (งงมาก)
    • $C[3,8]=\text{min}\{C[2,8],1+C[3,8-6]\}$

จะ Compare ในสมการก็ได้หรือว่าง่าย ๆ ก็คือ Compare ระหว่าง ข้างบนเรา กับ เลื่อนกลับไปจำนวน (ค่าของเหรียญนั้น ๆ) ช่อง!! แล้วหา Min นะ

Algorithm:

ALGORITHM CoinChange(n, N)
BEGIN
    for i=1 to n do C[i,0] = 0
    for i=1 to n do
        for j=1 to N do
        BEGIN
            c1 = C[i-1, j]
            c2 = 1 + C[i, j - d[i]]
            C[i, j] = min(c1, c2)
        END
    return C[n, N]
END.

Example

0/1 Knapsack Problem

• ก่อนหน้านี้เป็น Continuous (Fraction) Knapsack Problem
  • ก็คือสามารถเอาไปแค่บางส่วนของ Package ได้
  • แต่ 0/1 คือไม่สามารถเอาไปแค่บางส่วนได้ ได้แค่เอา/ไม่เอา จบ!!
• Given $n$ items with weights $w_1, w_2, ..., w_n$ and values $v_1, v_2, ..., v_n$, and a knapsack of capacity $W$, find the most valuable subset that fits.
• Define $V[i,j]$ as the maximum value obtained using the first $i$ items and a knapsack of size $j$.
• Recurrence relation: $$V[i,j] = \begin{cases} \max(V[i-1,j], v_i + V[i-1,j-w_i]) & \text{if } j \geq w_i \\ V[i-1,j] & \text{if } j < w_i \end{cases}$$

Example

Algorithm:

ALGORITHM Knapsack(v[1…n], w[1…n], W)
BEGIN
    for i=0 to n do V[i,0] = 0
    for j=0 to W do V[0,j] = 0
    for i=1 to n do
        for j=1 to W do
        BEGIN
            if (j < w[i]) then V[i,j] = V[i-1,j]
            else V[i,j] = max(V[i-1,j], v[i] + V[i-1, j - w[i]])
        END
    return V[n, W]
END.

Matrix Chain Multiplication

• ผลลัพธ์จะออกมาเป็นมิติ $\ce{m}\times\ce{p}$ (นอก)
• (ใน) ต้องเหมือนกัน จึงจะคูณกันได้

• อยากรู้ว่าต้อง Dot Product กี่ครั้ง?!

  • $2\times3\times2=12$ ก็จะเป็นจำนวน Dot Product ที่เกิดขึ้น

• สมมติมี Matrix $A_{2\times3}\times B_{3\times4}\times C_{4\times2}$

  • ควรเอาอะไรคูณอะไรก่อน Efficiency ก็จะต่างกันนะ!
  • ถ้าไม่เชื่อลองเอา $(A_{2\times3}\times B_{3\times4})\times C_{4\times2}$ กับ $A_{2\times3}\times (B_{3\times4}\times C_{4\times2})$ หาจำนวน Dot Product มันจะไม่เท่ากัน
    

• Given a sequence of matrices $A_1, A_2, ..., A_n$ with dimensions $p_0 \times p_1, p_1 \times p_2, ..., p_{n-1} \times p_n$, find the optimal way to parenthesize them to minimize multiplications.

• Key Idea: The order of multiplication affects efficiency, but the actual matrix multiplication is not performed—only the optimal order is determined.

Example

For matrices $A_1(10 \times 100)$, $A_2(100 \times 5)$, $A_3(5 \times 50)$:

1. Parenthesization: $(A_1 A_2) A_3$ → $10 \times 100 \times 5 + 10 \times 5 \times 50 = 7500$ multiplications.
2. Parenthesization: $A_1 (A_2 A_3)$ → $100 \times 5 \times 50 + 10 \times 100 \times 50 = 75000$ multiplications.
   • First parenthesization is 10x faster!

Algorithm

ALGORITHM matrix_chain(p)
BEGIN
    for i = 1 to n do
        m[i, i] = 0
    for l = 2 to n do
        for i = 1 to n - l + 1 do
        BEGIN
            j = i + l - 1
            m[i, j] = infinity
            for k = i to j-1 do
            BEGIN
                q = m[i, k] + m[k+1, j] + p[i-1] * p[k] * p[j]
                if q < m[i, j] then
                BEGIN
                    m[i, j] = q
                    s[i, j] = k
                END
            END
        END
    return m, s
END.

Floyd–Warshall algorithm

• Shortest path algorithm, เคยเรียนแล้วคือ Dijska แต่อันนั้นใช้ได้กับ Source เดียว
• แต่อันนี้ใช้ได้