문제를 본 날: 2022년 10월 25일

문제를 푼 날: 2022년 10월 25일

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

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?

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

Constraints:

• 1 <= n <= 45

Solution

각각의 걸음마다 우리가 선택할 수 있는 경우의 수는 두 가지가 있다.

1. 한 걸음을 올라간다.
2. 두 걸음을 올라간다.

dp[i]를 i걸음에서의 경우의 수라고 하자.

dp[i] = dp[i-1] + dp[i-2] 가 점화식이 될 것 같다. 마치 피보나치 수열 같다.