DP 기본 - (1로 만들기, 효율적인 화폐 구성)

DP란

1. 중복되는 연산을 줄이기 (top down방식의 memoization)
2. 작은 문제가 큰 문제의 부분이 되며 서로 영향을 미칠때( 분할 정복과 다른 점)
3. 대체적으로 점화식으로 나타낼수 있다.

예시

1.피보나치 수열

fn = fn-1 + fn-2의 점화식을 갖는다
top down방식으로 구현시 n==10일 때 2^10==1000 만큼 함수의 호출이 일어난다.
n== 100 이면 2^100 => (1000)^10 => 10^30으로 100년이 지나도 계산 불능

이떄 효율을 위하여 약간의 메모리를 사용하는 기법 메모이제이션(top down방식에서 유효하다)

또는 작은 부분(fn-1, fn-2)가 큰 부분 fn을 만든 다는 관점에서도 DP로 구현할수 있다(bottom up방식)

import java.io.*;

class Main {
  static long[] dp;
  
  public static void main(String[] args) throws IOException{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int N = Integer.parseInt(br.readLine());
    dp = new long[N+1];
    System.out.println("top down: " + topDown(N));
    System.out.println("bottomUP: " + bottomUp(N));
    
  }
  public static long topDown(int n){
    System.out.println("function " + n +" is called");
    if(n<3) return 1;
    if(dp[n]!=0) return dp[n];
    return dp[n] = topDown(n-1)+topDown(n-2);
  }
  public static long bottomUp(int n){
    if(n<3) return 1;
    long[] dpB = new long[n+1];
    dpB[1]=1;dpB[2]=1;
    for (int i=3; i<n+1; i++){
      dpB[i] = dpB[i-1]+dpB[i-2];
    }
    return dpB[n];
  }
}

2. 효율적인 화폐 구성

N가지 종류의 화폐가 주어질때 K를 주어진 화폐들을 이용하여 구성할 수있는
방법중 화폐의 수가 가장 작은 방법을 구하라

(1<=N<=100, 1<=K<=10,000)

import java.io.*;
import java.util.Arrays;

class Main {
  static int[] dp = new int[10001];
  static int[] coins;
  
  public static void main(String[] args) throws IOException{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    String[] strs = br.readLine().split(" ");
    Arrays.fill(dp,10001);
    int N=Integer.parseInt(strs[0]), K = Integer.parseInt(strs[1]);
    
    coins = new int[N];
    for (int i=0; i<N; i++){
      coins[i] = Integer.parseInt(br.readLine());
    }
    dp[0] = 0;
    for (int i=0; i<N; i++){
    /*
    갱신 가능한 화폐만 갱신
    */
      for(int j=coins[i]; j<K+1; j++){
        if(dp[j-coins[i]] != 10001){
          // (i-k)원을 만드는 방법이 존재 하는 경우
          dp[j]= Math.min(dp[j],dp[j-coins[i]]+1 );
        }
      }
    }

    if(dp[K] == 10001) System.out.println(-1);
    else System.out.println(dp[K]);
    
  }

}

for(int j=coins[i]; j<K+1; j++)
갱신 가능한 금액 구성만 갱신한다.