---
tags: Algorithm
---

<style>
font {
color: red;
}
</style>

# Ch03 - Dynamic Programming

## Dynamic Programming v.s. Divide and Conquer
### Differences
- **Divide-and-Conquer**
- **Top-Down**
- Blindly solves the divided instances by using recursion.
- Inefficient when the divided instances are related.
- Inefficient when the divided instances are almost as large as the original instance.
- **Dynamic Programming**
- **Bottom-Up** (solve small instances first, **store the results**, and later, whenever we need a result, look it up instead of re-computing it.)
- Programming (the use of an array in which a solution is constructed.)

## nth Fibonacci Term (Iterative)
Determine the nth term in the Fibonacci sequence.
> **Input:** a nonnegative integer `n`.
> **Output:** `fib2`, the nth term in the Fibonacci sequence.

int fib2 (int n) {
    index i;
    int f[0..n];
    
    f[0] = 0;
    if (n > 0) {
        f[1] = 1;
        for (i=2; i<=n; i++) {
            f[i] = f[i-1] + f[i-2];
        }
    }
    return f[n];     
}

**Time Complexity:** $T(n) = n + 1$

## Binomial Coefficient Using DP
Compute the binomial coefficient.
> **Input:** nonnegative integers `n` and `k`, where $k \le n$
> **Output:** `bin2`, the binomial coefficient $(^{n}_{k})$.

int bin2 (int n, int k) {
    index i, j;
    int B[0..n][0..k];
    
    for (i=0; i<=n; i++) {
        for (j=0; j<=minimum(i, k); j++) {
            if (j == 0 || i == 0) B[i][j] = 1;
            else B[i][j] = B[i-1][j-1] + B[i-1][j];
        }
    }
    return B[n][k];
}

> Review: [巴斯卡三角形](https://zh.wikipedia.org/zh-tw/%E6%9D%A8%E8%BE%89%E4%B8%89%E8%A7%92%E5%BD%A2)

## Floyd’s Algorithm for Shortest Paths
[最短路徑 演算法](https://ithelp.ithome.com.tw/articles/10209186)
- **Simple path**: a path that never passes through the same vertice twice.
- **Shortest Path Problem**
- **Example**:
- Air travelers want to determine the shortest way to fly from one city to another when a direct flight does not exist.

void floyd (int n, const number W[][], number D[][]) {
    index i, j, k;
    D = Ｗ;
    for (k=1; k<=n; k++) {
        for (i=1; i<=n; i++) {
            for (j=1; j<=n; j++) {
                D[i][j] = minimun(D[i][j], D[i][k] + D[k][j]);
            }
        }
    }
}

## Chained Matrix Multiplication

- 矩陣乘法的運算效率
- 當 $A \in M_{w \times x}, B \in M_{x \times y}$
- $A \times B$ 需要 $w \times x \times y$ 次乘法運算

<br>

- **Chained Matrix Multiplication**
- 多個矩陣相乘的運算
- 當矩陣排列順序相同時，相乘的先後順序不影響乘積
$$
ABC = (AB)C = A(BC)
$$
- 但是相乘的先後順序會影響運算的效率
$$
\text{For }
A \in M_{1 \times 2},\
B \in M_{2 \times 3},\
C \in M_{3 \times 4} \\
(AB) \in M_{1 \times 3},\ (BC) \in M_{2 \times 4}\\\ \\
\begin{split}
(AB)&:\ \ 1 \times 2 \times 3 &=\ 6
&\text{ multiplication} \\
(AB)C&: 6 + 1 \times 3 \times 4 &= 18
&\text{ multiplication}
\end{split}\\\ \\
\begin{split}
(BC)&:\ \ 2 \times 3 \times 4 &= 24
&\text{ multiplication} \\
A(BC)&: 24 + 1 \times 2 \times 4 &= 32
&\text{ multiplication}
\end{split}\\
$$
- **Minimum Multiplication**
- 尋找 Chained Matrix Multiplication 的 **最小運算次數** 的演算法
- 只找出 **怎麼算** 會最快，但是不會計算出相乘的結果

### Algorithm

- $A_i = d_{i-1} \times d_i$
- $M[i][j] =$ minimum number of multiplications meeded to multiple $A_i$ through $A_j$, if $i<j$
- $P[i][j] =$ the value of $k$ gave $M[i][j]$
$$
M[i][j] = \min_{i \le k \le k}(M[i][k]+M[k+1][j]+d_{i-1}d_kd_j)
$$


int minmult (int n,
            const int d[],
            index P[][])
{
    index i, j, k, diagonal;
    int M[1..n][1..n];
    
    for (i=1; i<=n; i++)
        M[i][i] = 0;
    for (diagonal = 1; diagonal <= n - 1; diagonal++)
        for (i = 1; i <= n - diagonal; i++) {
            j = i + diagonal;
            M[i][j] =
                min(M[i][k] + M[k+1][j] + d[i-1] * d[k] * d[j]);
            P[i][j] = k;
        }
    return M[1][n];
}

## Optimal Binary Search Tree (OBST)

The keys in a binary search tree are organized so that the average time it takes to locate a key is minimized.

:::success
**Definition:**
不同的插入順序會建構出不同的 BST，而在這些 BST 中，搜尋 node 花費的平均時間最短的就稱為 Optimal Binary Search Tree。
:::