Climbing Stairs - LeetCode

Problem

1. input: 정수 n

2. output: n 높이의 계단에 오를 수 있는 경우의 수 리턴

3. 한번에 1 ~ 2개의 계단을 오를 수 있다.

   • 1 <= n <= 45

Idea

한번에 오를 수 있는 최대 계단수가 2로 매우 적기 때문에 DP(Tabulation)으로 해결 → Sol1

⇒ 최대 이동 2 계단이므로 배열을 만들지 않고 2개의 변수에 -1, -2의 값을 저장하여 풀 수도 있음

Solution

1. DP(Tabulation)

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

   class Solution {
       fun climbStairs(n: Int): Int {
           if (n == 1) return 1
           if (n == 2) return 2
           val dp = Array<Int>(n + 1) { 0 }
           dp[1] = 1
           dp[2] = 2
           for (i in 3..n) {
               dp[i] = dp[i-1] + dp[i-2]
           }
           return dp[n]
       }
   }
   

   시간 복잡도: 1..n 순회 = n

   

Point