# 寫得很爛的參考用文章
所以只能參考用
### 文本內容
以下為提供語法班看的額外補充資料
可能會對這題有幫助
也可能不會

#### 遞迴與動態規劃(Recursive & DP)
這是一個「大事化小 小事化無」的解法
具體來說
我們會將較難的問題分解成小一點的 比較好理解或解決的問題
舉個栗子
「總共有n層階梯 你目前站在第0階
你每次可以選擇要走1階或是2階的階梯 請問你走到第n階有幾種方法數?」
思考一下就能發現
「走到第n階」只能透過「從第n-1階走一階上來」和「從第n-2階跨兩階上來」這兩個步驟來完成
若我們記F(n)為走到第n階的方法數
則F(n)=F(n-1)+F(n-2)
而且透過簡單計算可以知道F(1)=1, F(2)=2
這麼一來 我們知道它的規律
就能輕鬆求出所有答案了
他甚至只是個費氏數列
對了
階乘(!)也是遞迴喔

小結:

---

然而
遞迴是非常慢的
因為他會不斷的去call那些已經知道的東西
F(5)=F(4)+F(3)=( F(3)+F(2) )+F(3) (F3被叫了兩次)
所以會另外開設一個dp[]陣列
來存放我們已經知道的東西
我們可以寫說

dp[1]=1;
dp[2]=2;
for(int i=3;i<=n;i++){
    dp[i]=dp[i-1]+dp[i-2];
}

這樣只要跑n次就能得到答案了
這就是最基本的DP概念

---

#### 計數原理-乘法原理
:::spoiler {state="open"} 例題
從你家出發有8種公車路線可以到台中車站
並且台中車站有8個車次的火車可以到達整修過還是很醜的彰化車站

$\Rightarrow$你有==8 $\times$ 8=64==種方式可以到彰化車站
:::
像這種一次一次慢慢進行的行動
我們把每次小行動的方法數相乘
通常就能得到最終方法數

再來個栗子
今天有一隻青蛙和10片荷葉
青蛙一開始在其中一片荷葉上
他每次會往其他9片荷葉的其中一片跳
我們要求跳2次後回到一開始那片荷葉的跳法數

$\Rightarrow$第一跳有9種方法
但第二跳只能往原本的葉子跳

$\Rightarrow$總共有==9 $\times$ 1=9==個跳法

---

#### 快速冪
今天你想求$3^8$
你會慢慢的算$3\times 3\times 3\times 3\times 3\times 3\times 3\times 3$
還是把$3$平方平方再平方?
這就是快速冪的核心思想
與其一次一次自乘
不如用平方快速解決
那如果今天要求$487^{63}$呢?
我們拆成$487^{32} \times 487^{16} \times 487^8 \times 487^4 \times 487^2 \times 487$
其中較大的數都能透過小數平方得到
總共只要進行10次就能得到$487^{63}$囉(包括平方自乘與計算答案的相乘)

###### tags: `MDCPP` `Cosmos`