//
//  coin.c
//  coinDP
//
//  Created by vaibhav gautam on 11/28/14.
//  Copyright (c) 2014 vaibhav gautam. All rights reserved.
//
//  Given a list of N coins, their values (V1, V2, ... , VN),
//  and the total sum S. Find the minimum number of coins the sum of which is
//  S (we can use as many coins of one type as we want), or report that it's
//  not possible to select coins in such a way that they sum up to S.


#include <stdio.h>
#include <stdint.h>

int mincount(int change[], int changeSize, int SUM)
{
    int table[SUM + 1];
    
    table[0] = 0;
    int min = INT32_MAX;
    int sum = 0;
    int i = 0;
    int j = 0;
    
    for (sum = 1; sum <= SUM; sum++) {
        for (j = 0; j < changeSize; j++) {
            // Pick first coin and substract with the sum
            // Check if sum is less than 0
            if (sum - change[j] < 0) {
                continue;
            } else if (sum - change[j] == 0) {
                // This is the case when sum is either 1, 5, 10, 25
                // In this case mininum number of coin required is 1
                min = 1;
                break;
            }
            
            // This is case when we say sum is 3
            // In this case lets start with first coint which is 1
            // If we choose coint 1 then the sum left os 3 - 1 = 2
            // Given we are calculating for sum 3 means we have already
            // calculated for sum 2. So go to table for sum = 2 and
            // get the min number of ways sum 2 is computed.
            // Here i is the sum i.e. lets say as per our example
            // i = 3, j = 0
            // 1 + table[3 - change[0]];
            // 1 + table[3 - 1];
            // 1 + table[2];
            // 1 + 2 = 3
            // Sum 3 requires at least 3 coins {1, 1, 1}
            
            if (min > (1 + table[sum - change[j]])) {
                min = 1 + table[sum - change[j]];
            }
        }
        table[sum] = min;
        min = INT32_MAX;
    }
    
    for (i = 0; i <= SUM; i++) {
        printf("SUM[%d]: %d\n", i, table[i]);
    }
    
    return table[SUM];
}


int main(int argc, const char * argv[])
{
    int change[4] = {1, 5, 10, 25};
    int changeSize = sizeof(change)/sizeof(change[0]);
    int SUM = 16;
    
    printf("MinChange for sum %d = %d\n", SUM, mincount(change, changeSize, SUM));
    
    return 0;
}