[Leetcode(릿코드)] 70. Climbing Stairs (Easy)

leetcode.com/problems/climbing-stairs/

Climbing Stairs - LeetCode

---

문제

n이라는 숫자가 주어진다

그리고 이 숫자까지 올라갈 수 있는 경우의 수를 출력하는 문제이다

점프할 수 있는 수는 1과 2이다

예를 들어,

n=1, [1] (1개)

n=2, [1+1, 2] (2개)

n=3, [1+1+1, 1+2, 2+1] (3개)

n=4, [1+1+1+1, 1+2+1, 2+1+1, 1+1+2, 2+2] (5개)

 

해결

여기서 f(n)은 f(n-1)에서 1로 점프할 수 있고, f(n-2)에서 2로 점프할 수 있다

결국 f(n) = f(n-1)까지의 경우의 수 + f(n-2)까지의 경우의 수이다

dp 배열로 문제를 해결할 수 있다 O(N)

public int climbStairs(int n) {
    if (n==1 || n==2) return n;
    int[] dp = new int[n+1];
    dp[1] = 1;
    dp[2] = 2;
    for (int i=3; i<=n; i++)
        dp[i] = dp[i-1] + dp[i-2];
    return dp[n];
}