인프런 JAVA 알고리즘 정리(dp(동적계획법))

1. 계단오르기

 

복잡한 문제를 -> 작은 문제로 시작하여 푼다.  계단이 1개일때 부터 2개 3개 4개... 로 풀이

 

1번째 계단을 가는 경우의 수 : 1 가지

2번째 계단을 가는 경우의 수 : 2가지 ( 1칸 1칸, 2칸 )

3번째 계단을 가는 경우의 수 : 1번째 계단에서 올라오거나 or 2번째 계단에서 올라온다.

 -> 첫번째 계단 경우의 수 + 두번째 계단 경우의 수 

4번째 계단을 가는 경우의 수 : 2번 째 경우의 수+ 3번 째 경우의 수 

- 피보나치형식으로 구할수 있다. 

 

static int[] dy;
public static void main(String[] args) {
    Main T = new Main();
    Scanner kb = new Scanner(System.in);
    int n = kb.nextInt();
    System.out.println(solution(n));
}
public static int solution(int n){
    dy = new int[n+1];
    dy[1] = 1;
    dy[2] = 2;
    for(int i=3; i<=n; i++){
        dy[i] = dy[i-1]+dy[i-2];
    }
    return dy[n];
}