LeeCode - 70. Climbing Stairs(Array, Dynamic Program, Memoization)*

문제

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?

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

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

풀이

class Solution {
    public int climbStairs(int n) {
        if(n==1) return 1;
        if(n==2) return 2;
        
        int[] res = new int[n];
        
        res[0]=1;
        res[1]=2;
        
        for(int i=2;i<res.length;i++){
            res[i]=res[i-2]+res[i-1]; //피보나치
        }
        
        return res[n-1];
    }
}