# 演算法作業 HW12

---
## 第1題: shortest path in multi-stage graph

- 下圖為一個multi-stage graph，請分別以forward approach與backward approach，推導出點1到12的最短路徑。

### Ans:
1. forward approach:
- $d(1,12) = min\{9+d(2,12), 7+d(3,12), 3+d(4,12), 2+d(5,12)\}$

---
- $d(2,12) = min\{4+d(6,12), 2+d(7,12), 1+d(8,12)\}$
- $d(3,12) = min\{2+d(6,12), 7+d(7,12)\}$
- $d(4,12) = min\{11+d(8,12)\}$
- $d(5,12) = min\{11+d(7,12), 8+d(8,12)\}$
---
- $d(6,12) = min\{6+d(9,12), 5+d(10,12)\}$
- $d(7,12) = min\{4+d(9,12), 3+d(10,12)\}$
- $d(8,12) = min\{5+d(10,12),6+d(11,12)\}$
---

由上面結果得到:

- $d(6,12) = min\{6+4, 5+2\} = 7$
- $d(7,12) = min\{4+4, 3+2\} = 5$
- $d(8,12) = min\{5+2, 6+6\} = 7$

---
- $d(2,12) = min\{4+7, 2+5, 1+7\} = 7$
- $d(3,12) = min\{2+7, 7+5\} = 9$
- $d(4,12) = min\{11+7\} = 18$
- $d(5,12) = min\{11+5, 8+7\} = 15$

---

- $d(1,12) = min\{9+7, 7+9, 3+18, 2+15\} = 16$

2. backward approach

- $d(1,12) = min\{d(1,9)+4, d(1,10)+2, d(1,11)+6\}$

---

- $d(1,9) = min\{d(1,6)+6, d(1,7)+4\}$
- $d(1,10)= min\{d(1,6)+5, d(1,7)+3, d(1,8)+5\}$
- $d(1,11)= min\{d(1,8)+6\}$

---

- $d(1,6) = min\{d(1,2)+4, d(1,3)+2\}$
- $d(1,7) = min\{d(1,2)+2, d(1,3)+7, d(1,5)+11\}$
- $d(1,8) = min\{d(1,2)+1, d(1,4)+11, d(1,5)+8\}$

根據上面結果:

- $d(1,6) = min\{9+4, 7+2\} = 9$
- $d(1,7) = min\{9+2, 7+7, 2+11\} = 11$
- $d(1,8) = min\{9+1, 7+11, 2+8\} = 10$

---

- $d(1,9) = min\{9+6, 11+4\} = 15$
- $d(1,10)= min\{9+5, 11+3, 10+5\} = 14$
- $d(1,11)= min\{10+6\} = 16$

---
- $d(1,12) = min\{15+4, 14+2, 16+6\} = 16$

graph LR
    1 --> 3
    3 --> 6
    6 --> 10
    10 --> 12
    1 --> 2
    2 --> 7
    7 --> 10

## 第2題: leetcode70延伸
* 要上爬上10階的梯子，每一步可爬1階，2階，或3階，請問總共有幾種走法。
* 請仿照影片使用dp求解。
| 1 | 2 | 3 | 4 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| 1 | 1 | 2 | 4 | 7 | 13 | 24 | 44 | 81 | 149 | 274 |


## 第3題: Leetcode 1395應用
* 一個數列[4,2,5,3,6,1]，從其中挑出三個數，三數須要為遞增或遞減，請問有幾種挑選法？
* 請仿照影片使用dp求解