> For the complete documentation index, see [llms.txt](https://hannahpun.gitbook.io/leetcode-note/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hannahpun.gitbook.io/leetcode-note/dynamic-programing/70-climbing-stairs.md).

# # 70 Climbing Stairs

DP 題目實在太不熟，要多練習。租學者可以先用暴力解法，再找出其中規則

[LeetCode](https://leetcode.com/problems/climbing-stairs/)

```
You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Note: Given n will be a positive integer.

input: 總共 n 階, 你可以一次走一步或兩步 
output:  幾種方式可以到
```

```
Example 1:

Input: 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps
Example 2:

Input: 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step
*/

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {}
```

### 怎麼解

一看題目就覺得難果然是 DP ， DP 對我來說真的是太不熟練了。這題其實是變相費式數列

* n = 1, result 1 (爬一階 1 次) 
* n = 2, result 1 + 1 (爬一階 2 次 / 爬兩階 1 次) 
* n = 3, result 1 + 2 (前面兩個相加) (爬一階 3 次 / 爬兩階 1 次 + 爬一階 1 次 / 爬一階 1 次 + 爬兩階 1 次 ) 
* n = 4, result = 3 + 2 (前面兩個相加)

```
if(n == 1){
    return 1
}else if(n == 2){
    return 2
}
lookup[i] = lookup[i-1] + lookup[i-2]; 
```

是不是很像 XD

```javascript
var climbStairs = function(n) {
    if(n == 1){
        return 1
    }else if(n == 2){
        return 2
    }
    let lookup = [1,2]; // 1 step 有一種方式， 2 step 有兩種方式
    for(let i = 2; i< n ; i++){
        lookup[i] = lookup[i - 1] + lookup[i - 2]
    }
    return lookup[n - 1]
};
console.log(climbStairs(3))
```

9/25

```javascript
var climbStairs = function(n) {
    let cache = {}
    function innerGelper(n){
        if(cache[n]) return cache[n]
        if(n<=2) { 
            cache[n] = n
            return n
        }
        cache[n] = innerGelper(n-1) + innerGelper(n-2)
        return cache[n]
    }
   return innerGelper(n) 
};
```