[LeetCode] Climbing Stairs

문제

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

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

Note: Given n will be a positive integer.

Example 1:

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

Example 2:

Input: 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

 

Approach

계단을 한칸 혹은 두칸씩 올라갈 수 있으므로

n번째 계단은 n-1에서 한칸 올라가거나 n-2에서 두칸 올라갈 수 있다.

이는 곧 n = n-1 + n-2이다. (시간복잡도 O(n))

피보나치 수열인데 행렬곱으로 구현하면 훨씬 빠르지만(시간복잡도 O(logn))

이 문제는 행렬이 준비가 안되어 있으므로 생략

피보나치 행렬곱

행렬과 분할정복 기반의 피보나치 수 알고리즘

Code

https://github.com/chi3236/algorithm/blob/master/LeetCode_ClimbingStairs.cpp

chi3236/algorithm