DP- 계단타기

 

점화식을 구해보면 1 2 3 5 8 13 21 ---- 이렇게 증가하기 때문에 0번째 + 1번째 = 2번째 이 원리를 적용하면 답을 구할 수 있다.

 

import java.util.*;

public class kk {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int i = sc.nextInt();
        int a[] = new int[i+1];
         a[1]=1;
         a[2]=2;
         for(int w=3;w<=i;w++){
             a[w]=a[w-1]+a[w-2];
         }
        System.out.println(a[i]);




    }
}