[leetcode]70. Climbing Stairs

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

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) { 
    let count = 0;
    function recursive(total,current){
        if(total + current > n) return
        else if(total + current == n) {
            count +=1;
            return 
        }
        else{
           recursive(total+current,1)
           recursive(total+current,2)
        }
    }
    recursive(0,0)
    return count
};

단순 재귀 호출
공간복잡도 O(1)
시간복잡도 2^n

var climbStairs = function(n) { 
    let count = 0;
    const dp = Array(n).fill(0);
    dp[1] = 1;
    dp[2] = 2;

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

dp 활용
공간복잡도 O(n)
시간복잡도 O(n)

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) { 
    if (n < 3) return n
    let prev = 1;
    let current = 2;
    for(i=3;i<n+1;i++){
        let tempPrev = prev;
        prev = current;
        current = tempPrev + current
    }
    
    return current
};

슬라이딩 윈도우 기법
공간복잡도 O(1)
시간복잡도 O(n)

참고자료
https://kimstack.tistory.com/16
https://www.algodale.com/problems/climbing-stairs/