[JAVA] 알고리즘 : 동적 계획법- 돌다리 건너기

import java.util.Scanner;

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

 

여기서 주의해야 할 점은 돌다리의 개수까지만 경우의 수를 구하는 것이 아니라 개울을 건너야 하므로 돌다리의 개수+1까지의 경우의 수를 구해야 한다.

그렇기에 배열의 크기를 n+2로 하고 인덱스가 n+1일때의 총 경우의 수를 구한다.