---
# System prepended metadata

title: 演算法作業 HW12

---

# 演算法作業 HW12

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

- 下圖為一個multi-stage graph，請分別以forward approach與backward approach，推導出點1到12的最短路徑。
![](https://i.imgur.com/qnzsIEZ.png)

### 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$

```mermaid
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 |

![image](https://hackmd.io/_uploads/B1W3wFKrC.png)


## 第3題: Leetcode 1395應用
* 一個數列[4,2,5,3,6,1]，從其中挑出三個數，三數須要為遞增或遞減，請問有幾種挑選法？
* 請仿照影片使用dp求解
![image](https://hackmd.io/_uploads/ryA-dKFB0.png)
