DP - 아이템을 적절히 고르는 문제

 

지금까지 사용한 동전의 총 금액이 같다면 -> 동전이 적을수록 / 많을수록 더 좋다.

dp[i] = 지금까지 선택한 동전의 합이 i일때, 가능한 최대 동전의 개수.

 

dp[i] = max/min ( 0<=j<N i >= coin[j] ) dp[i - coin[j]] + 1

 

  for(int i=1; i<=M; i++) {
        for(int j=0; j<N; j++) {
            if(coin[j] > i || dp[i - coin[j]] == -1) continue;
            if(dp[i] == -1) {
                dp[i] = dp[i - coin[j]] + 1;
            }else {
                dp[i] = min(dp[i], dp[i - coin[j]] + 1);
            }
        }
    }

 

dp[0] = 0이고, 0을 기준으로 coin 배열의 첫 원소부터 끝까지 탐색하며 dp 배열을 갱신한다.

-> 원소의 개수가 무한, 중복된다는 가정.

중복 되지 않는 원소로 구할 수있는 최대/최소 합을 구하려면

위의 솔루션에서 M을 거꾸로 가게 하면 된다.

 

dp[0] = 0;
    for(int i=0; i<n; i++) {
        for(int j=m; j>=0; j--) {
            if(j >= A[i]) 
                dp[j] = min(dp[j], dp[j - A[i]] + 1);
        }
    }