# HW4 - Q6
###### tags: `演算法`, `109-2`

:::success
https://hackmd.io/@Cing-Chen/HJiVflpEu
:::

## Question

**Exercises 15.2-1**
Find an optimal parenthesization of a matrix-chain product whose sequence of dimensions is《5, 10, 3, 12, 5, 50, 6》.

## Mein Answer

:::info
為了方便星爆，我把題目的矩陣命名為以下代號
<br>
| 矩陣 Dimension | 5x10 | 10x3 | 3x12 | 12x5 | 5x50 | 50x6 |
|:--------------:|:----:|:----:|:----:|:----:|:----:|:----:|
| 對應代號 | A | B | C | D | E | F |

:::

### How to solve?
- 求表中目前元素的最佳解，如：ABC我們要比A(BC)或(AB)C孰能省力

| `x(i, j)` | A | B | C | D | E | F |
|:---------:|:---:|:---:|:---:|:----:|:-----:|:------:|
| **A** | A | AB | ABC | ABCD | ABCDE | ABCDEF |
| **B** | | B | BC | BCD | BCDE | BCDEF |
| **C** | | | C | CD | CDE | CDEF |
| **D** | | | | D | DE | DEF |
| **E** | | | | | E | EF |
| **F** | | | | | | F |

- `m(i, j)`是所需乘法次數
- `s(i, j)`是我們要達到最佳解的話，需要使用的m(i, j)中，j的值，在算式的意義上即是在誰的後面切一刀(加括號)
- `i`, `j` 是矩陣
- 讓我們一步一步來

#### Iteration 1
| `m(i, j)` | A | B | C | D | E | F |
|:---------:|:---:|:---:|:---:|:---:|:---:|:---:|
| **A** | 0 | | | | | |
| **B** | | 0 | | | | |
| **C** | | | 0 | | | |
| **D** | | | | 0 | | |
| **E** | | | | | 0 | |
| **F** | | | | | | 0 |

| `s(i, j)` | A | B | C | D | E | F |
|:---------:|:---:|:---:|:---:|:---:|:---:|:---:|
| **A** | | | | | | |
| **B** | | | | | | |
| **C** | | | | | | |
| **D** | | | | | | |
| **E** | | | | | | |
| **F** | | | | | | |

- 0 啦 都 0

#### Iteration 2

| `m(i, j)` | A | B | C | D | E | F |
|:---------:|:---:|:---:|:---:|:---:|:----:|:----:|
| **A** | 0 | 150 | | | | |
| **B** | | 0 | 360 | | | |
| **C** | | | 0 | 180 | | |
| **D** | | | | 0 | 3000 | |
| **E** | | | | | 0 | 1500 |
| **F** | | | | | | 0 |

| `s(i, j)` | A | B | C | D | E | F |
|:---------:|:---:|:---:|:---:|:---:|:---:|:---:|
| **A** | | A | | | | |
| **B** | | | B | | | |
| **C** | | | | C | | |
| **D** | | | | | D | |
| **E** | | | | | | E |
| **F** | | | | | | |

- 兩個相乘只會有一種可能的計算量

#### Iteration 3

| `m(i, j)` | A | B | C | D | E | F |
|:---------:|:---:|:---:|:---:|:---:|:----:|:----:|
| **A** | 0 | 150 | 330 | | | |
| **B** | | 0 | 360 | 330 | | |
| **C** | | | 0 | 180 | 930 | |
| **D** | | | | 0 | 3000 | 1860 |
| **E** | | | | | 0 | 1500 |
| **F** | | | | | | 0 |

| `s(i, j)` | A | B | C | D | E | F |
|:---------:|:---:|:---:|:---:|:---:|:---:|:---:|
| **A** | | A | B | | | |
| **B** | | | B | B | | |
| **C** | | | | C | D | |
| **D** | | | | | D | D |
| **E** | | | | | | E |
| **F** | | | | | | |

- 這裡開始有比較出現了，拿 A-C 格為例，有 (AB)C 或 A(BC) 兩種可能
- (AB)C: 查表 AB=150 (AB)C=`150+5*3*12`=`150+180`=330
- A(BC): 查表 BC=360 A(BC)=`360+5*10*12`=`360+600`=960
- 我們取兩者最低的330，並把下括號左邊的矩陣（這裡是B）放到s表
- 好，之後我們就知道ABC的最短行動數是 330，而不會管是怎麼做到的
- 要管怎麼作到的話，沿 s 表爬回去
- 剩下的就照本宣科

#### Iteration 4

| `m(i, j)` | A | B | C | D | E | F |
|:---------:|:---:|:---:|:---:|:---:|:----:|:----:|
| **A** | 0 | 150 | 330 | 405 | | |
| **B** | | 0 | 360 | 330 | 2430 | |
| **C** | | | 0 | 180 | 930 | 1770 |
| **D** | | | | 0 | 3000 | 1860 |
| **E** | | | | | 0 | 1500 |
| **F** | | | | | | 0 |

| `s(i, j)` | A | B | C | D | E | F |
|:---------:|:---:|:---:|:---:|:---:|:---:|:---:|
| **A** | | A | B | B | | |
| **B** | | | B | B | B | |
| **C** | | | | C | D | D |
| **D** | | | | | D | D |
| **E** | | | | | | E |
| **F** | | | | | | |

- ABCD => 比 (ABC)D 或 A(BCD)

#### Iteration 5

| `m(i, j)` | A | B | C | D | E | F |
|:---------:|:---:|:---:|:---:|:---:|:----:|:----:|
| **A** | 0 | 150 | 330 | 405 | 1655 | |
| **B** | | 0 | 360 | 330 | 2430 | 1950 |
| **C** | | | 0 | 180 | 930 | 1770 |
| **D** | | | | 0 | 3000 | 1860 |
| **E** | | | | | 0 | 1500 |
| **F** | | | | | | 0 |

| `s(i, j)` | A | B | C | D | E | F |
|:---------:|:---:|:---:|:---:|:---:|:---:|:---:|
| **A** | | A | B | B | D | |
| **B** | | | B | B | B | B |
| **C** | | | | C | D | D |
| **D** | | | | | D | D |
| **E** | | | | | | E |
| **F** | | | | | | |

#### Iteration 6 <!--AF決戰-->

| `m(i, j)` | A | B | C | D | E | F |
|:---------:|:---:|:---:|:---:|:---:|:----:|:----:|
| **A** | 0 | 150 | 330 | 405 | 1655 | 2010 |
| **B** | | 0 | 360 | 330 | 2430 | 1950 |
| **C** | | | 0 | 180 | 930 | 1770 |
| **D** | | | | 0 | 3000 | 1860 |
| **E** | | | | | 0 | 1500 |
| **F** | | | | | | 0 |

| `s(i, j)` | A | B | C | D | E | F |
|:---------:|:---:|:---:|:---:|:---:|:---:|:---:|
| **A** | | A | B | B | D | B |
| **B** | | | B | B | B | B |
| **C** | | | | C | D | D |
| **D** | | | | | D | D |
| **E** | | | | | | E |
| **F** | | | | | | |

### Answer

- 根據上面s表，從AF開始爬，看出我們要先從B後面切一刀，變成 (AB)(CDEF)
- 接著，為了找到CDEF的解，我們爬s表的CF，決定從D後面切一刀，變成(AB)((CD)(EF))
- 好耶！ 答案就是`(AB)((CD)(EF))`，需要 `2010` 次乘法
- 或是 `((5×10)(10×3))(((3×12)(12×5))((5×50)(50×6)))`

### References
- [矩陣鏈乘積 - 維基百科](https://zh.wikipedia.org/wiki/%E7%9F%A9%E9%99%A3%E9%8F%88%E4%B9%98%E7%A9%8D)
- [4.3 Matrix Chain Multiplication - Dynamic Programming](https://youtu.be/prx1psByp7U)
- CLRS 15-2