동적계획법

동적계획법

큰 문제를 작은 문제로 나누었을 때 동일한 작은 문제가 반복해서 등장
일정한 규칙 => 점화식
완전탐색으로 하면 시간 초과 -> 가지치기 -> 안된다면 DP, memoization

분할 정복과는 다름 - 앞뒤 선후 관계가 존재하지 않음

ex.
피보나치 순열

package basic.dp;

public class Fibo {
    public static void main(String[] args) throws Exception {
//        long res = fibo(50);
        long res = fibo_momo(50);
        System.out.println(res);
    }
    // 시간 초과
    static long fibo(int n){
        if(n==1||n==2) return 1;
        return fibo(n-1)+fibo(n-2);
    }
    // memoization
    static long[] memo = new long[51];
    static long fibo_momo(int n){
        if(n==1||n==2) return 1;
        if(memo[n]>0) return memo[n];
        else return memo[n] = fibo_momo(n-1)+fibo_momo(n-2);
    }
    // DP
    static long[] dp = new long[51];
    static long fibo_dp(int n){
        dp[1] = 1;
        dp[2] = 1;
        for(int i=3;i<=n;i++){
            dp[i] = dp[i-1]+dp[i-2];
        }
        return dp[n];
    }
}