Dynamic Programming(동적계획법) - 계단오르기

 

 계단오르기

 

import java.util.*;

class Main{
    // Dynamic Programming(동적계획법)
    // 큰문제를 한 번에 못 풀기 때문에 작은 단위로 쪼갠다.
    static int[] dy;
    public int solution(int n){
        // 직관적으로 초기화
        dy[1]=1;
        dy[2]=2;
        for(int i=3; i<=n; i++) dy[i]=dy[i-2]+dy[i-1];
        return dy[n];
    }

    public static void main(String[] args){
        Main T = new Main();
        Scanner kb = new Scanner(System.in);
        int n=kb.nextInt();
        dy=new int[n+1];
        System.out.print(T.solution(n));
    }
}