You are climbing a staircase that has n steps. You can take the steps either 1 or 2 at a time. Calculate how many distinct ways you can climb to the top of the staircase.

Example

• For n = 1, the output should be

  solution(n) = 1;

• For n = 2, the output should be

  solution(n) = 2.

  You can either climb 2 steps at once or climb 1 step two times.

Input/Output

• [execution time limit] 3 seconds (java)

• [memory limit] 1 GB

• [input] integer n

  Guaranteed constraints:

  1 ≤ n ≤ 50.

• [output] integer

  It's guaranteed that the answer will fit in a 32-bit integer.

풀이

int solution(int n) {
    if (n == 1) return 1;
    if (n == 2) return 2;
    
    int [] arr = new int [n + 1];
    // 1 step
    arr[1] = 1;
    // 1, 1 steps
    // 2 steps
    arr[2] = 2;
    
    for (int i = 3; i <= n; i ++) {
        arr[i] = arr[i - 1] + arr[i - 2];
    }
    
    return arr[n];
}