[c++/LeetCode-DP] 70. Climbing Stairs

 

 

 

 

난이도: Easy

키워드: DP

 

 

 

 

📍 문제

 

계단을 오르고 있습니다. 꼭대기에 도달하기 위해 n개의 단계가 필요합니다.
각 단계마다 1개 또는 2개의 단계를 오를 수 있습니다. 꼭대기에 도달하는 데 몇 가지 다른 방법이 있는지 계산하세요.

 

Example 1:

Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

 

Example 2:

Input: n = 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

 

문제 원문: https://leetcode.com/problems/climbing-stairs/description/

 

📍 문제 풀이

 

기본적인 DP 문제이다. 문제를 재귀 함수로 표현할 수 있는지를 파악한 후 Top-down. 혹은  Bottom-up 방식으로 해를 찾을 수 있다.

일반적으로 Bottom-up이 더 빠르기 때문에 bottom up으로 코드를 짰다.

 

a[n]을 n번째 계단까지 가는 데 가능한 방법 수라고하면

a[n] = a[n-2] + a[n-1]을 만족하므로

 

class Solution {
public:
    int climbStairs(int n) {

        vector<int> a(n+1, 0);
        if(n == 1) return 1;
        if(n == 2) return 2;
        a[0] = 1;
        a[1] = 1;
        a[2] = 2;

        for(auto i = 3; i < (n+1); ++i){
            a[i] = a[i-1] + a[i-2];
        }

        return a[n];
    }
};