---
# System prepended metadata

title: Dynamic Programming
tags: [知識分享會]

---

---
tags: 知識分享會
---

# Dynamic Programming

定義：將動態規劃在尋找有很多**重疊子問題**的情況的最佳解時有效。它將問題重新組合成子問題。為了避免多次解決這些子問題，它們的結果都逐漸被計算並被儲存，從簡單的問題直到整個問題都被解決。因此，動態規劃儲存遞迴時的結果，因而不會在解決同樣的問題時花費時間。

> 優化的演算法，把重複的結果儲存下來，以便提升效率。


---

## Fibonacci Sequence



```=js
// 1, 1, 2, 3, 5, 8, ...

fib(3)
> 2
fib(5)
> 5
```

### Steps to do it
1. Recursion
2. Store (Memoize)
3. Bottom-up


### 1. Recusion

![](https://i.imgur.com/Xj4apzo.png)


### Coding Time

https://leetcode.com/problems/min-cost-climbing-stairs/


