[LeetCode] Climbing Stairs

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

Climbing Stairs - LeetCode

 

난이도 Easy로 상당히 쉬운 문제입니다.

 

class Solution {
public:
    int dp[46];
    int climbStairs(int n) {
        dp[0] = 1; dp[1] = 1;
        for(int i = 2; i <= n; ++i){
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n];
    }
};

1) table 정의

dp[i] : 높이 0에서 시작하여 높이 i인 top에 도달할 수 있는 방법의 수

 

2) 점화식 찾기

dp[i] = dp[i-1] + dp[i-2];

높이 i에 도달하는 방법의  수 = 높이 i-1에서 1step 올라가는 방법의 수 + 높이 i-2에서 2step 올라가는 방법의 수

 

3) 초기값 설정

dp[0] = 1; dp[1] = 1;

 

시간복잡도와 공간복잡도 모두 O(n)입니다. 

 

이 문제에서는 공간복잡도 O(n)의 배열을 사용하지 않아도 다음과 같이 구현하면 공간복잡도 O(1)에 해결이 가능합니다. 다만, 시간복잡도는 동일하게 O(n)입니다.

class Solution {
public:
    int climbStairs(int n) {
        int a = 1, b = 1, tmp;
        for(int i = 2; i <= n; ++i){
            tmp = b;
            b += a;
            a = tmp;
        }
        return b;
    }
};