[Dynamic Programming][Easy] 70. Climbing Stairs

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

 

 

Q. 한번에 하나 혹은 두개의 계단을 올라갈 수 있을때, n 개의 계단을 모두 오르는 경우의 수를 계산하라. 

 

Solution. 

 완료 조건 경우의 수를 찾는 문제. 

 DP의 일반적 문제 중의 하나다. 

 

 특정 위치에서 하나의 계단을 밟아 나가거나, 

 두개의 개단을 밟아 나가거나 두개의 선택만이 존재 한다. 

 종료 조건은?

 다 올라가는 것이므로, 현재 계단이 n 보다 크거나 같으면 1회 달성 한 것이다. 

 

 로직대로 코드를 써 주고 벡터 캐시로 최적화를 한다. 

 

 

    int climbStairs_helper(int n, vector<int>& vCache, int cur)
    {
        if(cur >= n)    return 1;
        if(vCache[cur] >= 0)
            return vCache[cur];

        vCache[cur] = climbStairs_helper(n, vCache, cur+1) + climbStairs_helper(n, vCache, cur+2);
        return vCache[cur];
    }

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

 

 

적절한 결과를 얻었다.