70. Climbing Stairs

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

Climbing Stairs - LeetCode

 

정수로 주어진 n개의 계단을 1계단 또는 2계단씩 올라가려고 한다. 몇 가지 방법으로 올라갈 수 있는지 구하는 문제다.

 

먼저 n개의 계단을 올라갈 수 있는 방법은 2가지가 있다.

첫번째, 1개의 계단을 오르고 N-1계단을 올라가는 방법

두번째, 2개의 계단을 오르고 N-2계단을 올라가는 방법

T(n) = T(n-1) + T(n-2)

고로 이 식으로 전체 수를 구하면 된다.

 

하지만 재귀를 통해 단순히 풀게되면 중복 계산이 너무 많아진다.

T(5) = T(4) + T(3)

T(4) = T(3) + T(2)

...

 

이미 저장한 값을 별도 캐시(map, vector, arr등등)에 저장하고 이미 계산되어있는건 갖다쓰자.

 

class Solution {
public:
    int solve(int n) {
        if (v_[n] != 0) {
            return v_[n];
        }
        
        int ret = 0;
        if (n == 0) {
            ret = 0;
        }
        else if (n == 1) {
            ret = 1;
        }
        else if (n == 2) {
            ret = 2;
        }
        else {
            ret = solve(n-1) + solve(n-2);
        }
        
        v_[n] = ret;
        return ret;
    }
 
    int climbStairs(int n) {
        v_.resize(n + 1, 0);
        solve(n);
        return v_[n];
    }

private:
    vector<int> v_;
};