Leetcode Algorithm no.70— Climbing Stairs

Climbing Stairs - LeetCode

Brute Force (Top-down)

index가 증가하는 Top-down방식. 마지막 종료 case에 유의한다. 완전 탐색이므로 시간 복잡도는 재귀 트리의 사이즈인 O(2^N), 공간 복잡도는 재귀 트리의 깊이만큼인 O(N).

//Java
class Solution {
    public int climbStairs(int n) {
        return climb_stairs(0, n);
    }
    
    public int climb_stairs(int i, int n){        
        if(i > n){
            return 0;
        }
        if(n == i){
            return 1;
        }
        return climb_stairs(i+1, n) + climb_stairs(i+2, n);
    }
}
//JavaScript ES6
/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
    return climb_stairs(0, n);
};
function climb_stairs(start, end){
    if(start > end) return 0;
    if(start == end) return 1;
   return climb_stairs(start+1, end) + climb_stairs(start+2, end);
}

Brute Force with memoization

memoization한 배열을 넘겨주는 것을 잊지말도록 한다. memoization을 사용하여 한 번 계산한 것은 다시 계산하지 않으므로 시간 복잡도는 O(N²)에서 O(N)으로 감소, 공간 복잡도는 그대로 O(N).

//Java
class Solution {
    public int climbStairs(int n) {
        int[] memo = new int[n+1];
        return climb_stairs(0, n, memo);
    }
    
    public int climb_stairs(int i, int n, int[] memo){        
        if(i > n){
            return 0;
        }
        if(n == i){
            return 1;
        }
        if(memo[i] > 0){
            return memo[i];
        }
        memo[i] = climb_stairs(i+1, n, memo) + climb_stairs(i+2, n, memo); 
        return memo[i];
    }
}
//JavaScript ES6
/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
    return climb_stairs(0, n);
};
function climb_stairs(start, end, memo = []){
    if(start > end) return 0;
    if(start == end) return 1;   
    if(memo[start]){
        return memo[start];
    }else{
        memo[start] = climb_stairs(start+1, end, memo) + climb_stairs(start+2, end, memo);   
        return memo[start];    
    }
}

Dynamic Programming (Bottom-up)

index가 감소하므로 Bottom-up 방식이며, 시작 지점인 base case 작성에 유의 하도록 한다. 시간 복잡도는 n까지 한 번만 반복하므로 O(N), 공간 복잡도는 n size만큼의 배열이 사용되므로 O(N).

//Java
class Solution {
    public int climbStairs(int n) {
        if(n==1){
            return 1;
        }
        int[] dp = new int[n+1];
        dp[1] = 1;
        dp[2] = 2;
        for(int i = 3; i<=n; i++){
            dp[i] = dp[i-1]+dp[i-2];
        }
        return dp[n];
    }
}
//JavaScript ES6
/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n, memo = []) {
    if(n==1) return 1;
    let dp = [null,1,2];
    for(let i = 3; i<=n; i++){
        dp[i] = dp[i-1]+dp[i-2];
    }
    return dp[n];
};

Fibonacci method

1과 2에서 시작한다는 것을 유의할 것. 변수 두 개를 이용해 공간 복잡도를 O(1)까지 줄일 수 있음. 시간 복잡도는 N번째 피보나치 숫자를 계산하기 위해 N번의 반복이 요구되므로 O(N).

//Java
class Solution {
    public int climbStairs(int n) {
        if(n == 1){
            return 1;
        }
        int first = 1;
        int second = 2;
        for (int i = 3; i <= n; i++){
            int third = first + second;
            first = second;
            second = third;
        }
        return second;
    }
}
//JavaScript ES6
/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
    if(n == 1){
        return 1;
    }
    let first = 1;
    let second = 2;
    for(let i = 3; i<=n; i++){
        const third = first+second;
        first = second;
        second = third;        
    }
    return second;
    
};