[Leet Code Top 100] #70. Climbing Stairs

문제 정보

• Leet Code 문제 링크
• 난이도 : Easy

 

해결 방법

문제 자체가 기본적인 Dynamic Programming 의 꼴을 하고 있어서 그렇게 구현했습니다. dp 함수를 따로 사용하지 않고 배열에 for loop 를 순회하면서 데이터를 채워 넣어도 구현이 가능합니다.

 

소스 코드

// Leet Code
// #70. Climbing Stairs
// Success
// Runtime: 72 ms, faster than 74.80% of JavaScript online submissions for Climbing Stairs.
// Memory Usage: 38.6 MB, less than 58.88% of JavaScript online submissions for Climbing Stairs.

function main(){
    // Input // Output
    n = 3; // 3

    console.log(climbStairs(n));
}

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
    const memo = [];
    const dp = function(n){
        if(n === 1 || n === 2) memo[n] = n;
        if(!memo[n]) memo[n] = dp(n - 1) + dp(n - 2);
        return memo[n];
    }
    return dp(n);
};

main();

 

참고 자료

• LeetCode Top 100 Problem Selection
• LeetCode - Python different solutions (bottom up, top down).