[알고리즘] DP 알고리즘

DP, Dynamic Programming(동적 계획법)이란, 하나의 큰 문제를 작은 문제로 나누어 해결하는 기법이다.

DP를 구현하는 방법은 두 개가 있다. 각각 Top-Down 방식과 Botton-Up 방식이다.

 

Top-Down

- 재귀함수

import java.util.Scanner;

public class FibonacciTopDown {

    static int[] memo;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        memo = new int[n + 1];
        
        for (int i = 0; i <= n; i++) {
            memo[i] = -1;
        }
        
        System.out.println(fib(n));
    }

    public static int fib(int n) {
        if (n <= 1) {
            return n;
        }
        if (memo[n] != -1) {
            return memo[n];
        }
        memo[n] = fib(n - 1) + fib(n - 2);
        return memo[n];
    }
}

 

Botton-Up

- for 반복문

import java.util.Scanner;

public class FibonacciBottomUp {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        System.out.println(fib(n));
    }

    public static int fib(int n) {
        if (n <= 1) {
            return n;
        }

        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 1;

        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }

        return dp[n];
    }
}

 

백준 사이트에서 문제를 풀어보면 좋을 것 같다.

https://www.acmicpc.net/workbook/view/7836