[알고리즘 문제풀이]Dynamic Programming

1. 계단 오르기

🚩 내 코드

import java.util.Scanner;

public class 계단오르기 {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] dy = new int[n+1];
        dy[1] = 1;
        dy[2] = 2;

        for(int i=3; i<=n; i++){
            dy[i] = dy[i-2]+dy[i-1];
        }
        System.out.println(dy[n]);
    }
}

💡 푼 방식

그 이전꺼를 이용하는 방식.

📚 알게 된 정보

피보나치 같당

2. 돌다리 건너기

🚩 내 코드

import java.util.Scanner;

public class 돌다리건너기 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int dy[] = new int[n+1];
        dy[0] = 1;
        dy[1] = 2;
        for(int i=2; i<=n; i++){
            dy[i] = dy[i-2]+dy[i-1];
        }
        System.out.println(dy[n]);
    }
}

💡 푼 방식

위의 문제와 방식은 같다.
그치만 땅으로 가려면 마지막 돌다리에서 한번 더 건너야한다는 것을 주의하자~