---
# System prepended metadata

title: 遞精喔喔喔喔喔喔
tags: [110程式設計一]

---

# 遞精喔喔喔喔喔喔
---
[TOC]
###### tags: `110程式設計一`

---
## 一般遞迴
code is here:
```c=

int climbStairs(int n){
    if(n < 4)
        return n;
    else
        return climbStairs(n - 1) + climbStairs(n - 2);
}
```
我們先發現這題跟費氏數列一樣

---

### Submission in Leetcode:
![](https://i.imgur.com/75BkhTX.png)


---

## 遞迴記憶
code is here:
```c=
int cache[46] = {0};
int climbStairs(int n){
    
    
    if(n < 4)
        return n;
    if (cache[n] > 0)
        return cache[n];
    else
        cache[n] = climbStairs(n - 1) + climbStairs(n - 2);
    return cache[n];
}
```

---

### Submission in Leetcode:
![](https://i.imgur.com/gohcUsq.png)

## DP(動態規劃):

code is here:

```c=
int climbStairs(int n){
    if(n < 4)
        return n;
    int prv = 1;
    int after = 2;
    int res;
    for(int i = 3; i <= n ;i++){
        res = prv + after;
        prv = after;
        after = res;
    }
    return res;
}
```

---

### Submission in Leetcode:
![](https://i.imgur.com/6KI5v2T.png)

稍微優化一下

---

## DP優化
code is here:
```c=
int climbStairs(int n){
    if(n < 4)
        return n;
    int prv = 2;
    int after = 3;
    int res;
    for(int i = 4; i <= n ;i++){
        res = prv + after;
        prv = after;
        after = res;
    }
    return res;
}
```

---

### Submission in Leetcode:
![](https://i.imgur.com/94b3XhB.png)
