[1D DP][Easy] 70. Climbing Stairs

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

 

한번에 1개 혹은 2개의 계단을 밟을 수 있다고 할 때, 계단을 다 오를 모든 경우의 수를 찾아라.

 

리마인드 하듯이 문제를 풀어 본다. 

 

DP 문제는 복합적인 듯한 문제를 단일 단계로 해석하는 것이 중요하다. 

 

한 단계에서 1개 혹은 2개만 올라 갈 수 있다. 

또한 끝까지 오르면 그만 둔다. 

따라서 특정 단계에서 오른 횟수를 구한다면, 그 값을 재활용 할 수 있다.

(마지막 계단 바로 앞에서는 1회 두 번, 2회 한번의 두 가지 경우가 존재하고, 이것은 이 전에 무엇을 했던 동일하다.)

 

코드 

int climb(vector<int>& vCache, int idx, int n)
{
    if(idx >= n)
        return 1;

    if(vCache[idx] >= 0)
        return vCache[idx];

    int ret = climb(vCache, idx + 1, n);
    ret += climb(vCache, idx + 2, n);
    vCache[idx] = ret;
    return ret;
}

int climbStairs(int n) 
{
    vector<int> vCache;
    vCache.resize(n, -1);
    return climb(vCache, 1, n);
}

 

 

결과