[LeetCode] 70. Climbing Stairs

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

Climbing Stairs - LeetCode

leetcode - Climbing Stairs

문제 유형 : 다이나믹 프로그래밍

문제 난이도 : Easy

 

문제

You are climbing a staircase. It takes n steps to reach the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

 

당신은 계단을 오른다. n칸을 올라야 한다.

1칸이나 2칸씩 오를 수 있다.

몇 가지의 경우의 수가 존재하는지 구하시오.

 

 

풀이

시작 지점(0칸)의 경우의 수는 1,

1칸째의 경우의 수도 1이다.

2칸째에서는 0칸에서 2칸씩 오르는 경우와, 1칸째에서 1칸 오르는 경우를 더하면 된다.

3칸째에서는 1칸에서 2칸씩, 2칸에서 1칸 오르는 경우를 더하면 된다.

n칸에서는 n-2칸에서 2칸씩, n-1칸에서 1칸 오르는 경우를 더하면 된다.

 

바텀업 dp로 풀어주면 된다.

 

코드

C++

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