dp_coins_tc_2.cpp

/* Coin Change - Version I */
/* Author : M. A. Rafsan Mazumder */

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n;
    scanf("%d", &n);
    int arr[n];
    for(int i=0; i<n; i++) scanf("%d", &arr[i]);
    int tot;
    scanf("%d", &tot);
    int res[tot+1];
    for(int i=1; i<=tot; i++) res[i] = INT_MAX;
    res[0] = 0; //Important
    for(int i=1; i<=tot; i++){
        for(int j=0; j<n; j++){
            if(i - arr[j] >= 0){
                if(res[i-arr[j]] + 1 < res[i]) res[i] = res[i-arr[j]] + 1;
            }
        }
    }
    cout << res[tot];
}