[LeetCode] 70 - Climbing Stairs

문제

• 링크: https://leetcode.com/problems/climbing-stairs
• 난이도: Easy
• 태그: 수학, 다이내믹 프로그래밍, 메모이제이션
• 결과: Time: 0 ms (100%), Space: 7.87 MB (69.70%)

풀이

class Solution {
public:
    int climbStairs(int n) {
        int p = 1;
        int pp = 0;
        int cur = 0;
        for (int i = 0; i < n; ++i)
        {
            cur = p + pp;
            pp = p;
            p = cur;
        }

        return cur;
    }
};

피보나치 수열과 같다. d[n]을 n번째 칸까지 계단을 오르는 경우의 수라고 하자. n번째 칸에 도달하려면 n - 1번째 칸에서 1칸 오르거나, n - 2번째 칸에서 2칸을 올라야하므로 d[n] = d[n - 1] + d[n - 2]가 된다.

이 포스트는 달레 스터디(2주차)에서 진행한 Blind 75 문제집 풀이의 일부입니다.