# 70 Climbing Stairs

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

LeetCode

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

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

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) 
};