Minimum number of coins problem using dynamic programming - follow up

Question

I previously posted a code here. It turns out that the code is not following the correct dynamic programming principles and instead it was based on a greedy approach. Hence, I started again, keeping in mind helpful guidelines from here and here. I would now like to know if my code is efficient, or if it can be further optimized in terms of time and space complexity.

#include <stdio.h>
#include <stdlib.h>

int i , no_of_denominations , denominations [ 10000 ] , total_cost , cost [ 10000 ] ;

int min ( int idx )
{
    int min_cost = 99999 , j ;
    cost [ 0 ] = 0 ;
    for ( j = 0 ; j < no_of_denominations ; j++ )
    {
        if( ( i >= denominations [ j ] ) && ( min_cost > cost [ i - denominations [ j ] ] ) )
        {
            min_cost = cost [ i - denominations [ j ] ] ;
        }
    }
    return min_cost ;
}

void input()
{
    printf ( "Coin Change with min no. of coins\nEnter the total change you want: " ) ;
    scanf ( "%d" , &total_cost ) ;

    printf ( "Enter the no. of different denominations of coins available: " ) ;
    scanf ( "%d" , &no_of_denominations ) ;

    printf ( "Enter the different denominations in ascending order: \n" ) ;
    for ( i = 0 ; i < no_of_denominations ; i++ )
    {
        scanf ( "%d" , &denominations [ i ] ) ;
    }
}

void calc_print ()
{
    for ( i = 1 ; i <= total_cost ; i++ )
     {
         cost [ i ] = 1 + min ( i ) ;
     }

     printf ( "min no of coins = %d" , cost [ total_cost ] ) ;
}

int main()
{
    input () ;
    calc_print () ;
    return 0;
}

Answer 1

I advised you that it is called main and not everything, and you did a good job of moving code out of main. Now main looks a lot closer to what I'd expect to see.

But, we still have functions that are doing too much. Plus, we've made a bad problem worse. We've replaced doing everything in the main function with global variables. And we don't want to do that.

---

One indication that we have functions that are doing too much is that our functions don't have very great names and there's not a good name to give to them.

For example, void input(). It's not very clear what exactly this function does (from name alone), and we can't really give it a more clear name without it being miles long (and filled with ands... "and" and "or" in function names is generally a code smell). From the name alone, we'd guess that this function gets input from the user. But what does it do with that input? Who knows? Because this returns void and it doesn't take anything by reference to return either.

So let me repeat the method from earlier more clearly (this you can and should copy-and-paste this exactly and use it):

int getUserInput(const char * prompt) {
    int input;
    printf(prompt);
    scanf("%d", input);
    return input;
}

Do not mistake this. You're repeatedly getting integer input from the user. This is a clear indication that you should have a function for doing this. If you don't have this in your next post, you're doing something very wrong.

The section in which we gather inputs from the user should look basically exactly like this:

int denominationCount = getUserInput("How many different denominations? ");
for (int i = 0; i < denominationCount; ++i) {
    denominations[i] = getUserInput("Enter the next denomination: ");
}
int makingChangeFor = getUserInput("How much are we making change for? ");

And now you've got all the values for which to do the calculation. You can feed them to the function that does the calculation and get an output from that. And you don't need the global variables.

Until all of your functions that are accessing the global variables are both taking and returning arguments, you shouldn't be comfortable using the global variables (as a rough guideline). Global variables are almost always unnecessary. Global variables are the path to rats nests, madness, and lunacy.

Answer 2

The first thing I can say is that you didn't listened to me.

Look at this block:

for ( i = 0 ; i < no_of_denominations ; i++ )
{
    scanf ( "%d" , &denominations [ i ] ) ;
}

What did I say? Declare variables as close to where you will use them as possible.

You should have this:

for ( int i = 0 ; i < no_of_denominations ; i++ )
{
    scanf ( "%d" , &denominations [ i ] ) ;
}

See? It doesn't kill you and your compiler will be happy!

---

Still, there is no validation of the data. And there's no way to pick 0.5€ (50 cents).

You should look into that.

---

But not everything is bad. You heard me about bad naming and missing whitespace.

But now you have a new problem: too much whitespace!

Look at this:

int min_cost = 99999 , j ;
cost [ 0 ] = 0 ;
for ( j = 0 ; j < no_of_denominations ; j++ )
{
    if( ( i >= denominations [ j ] ) && ( min_cost > cost [ i - denominations [ j ] ] ) )
    {
        min_cost = cost [ i - denominations [ j ] ] ;
    }
}

How can I read this? Where is everything closing and opening?

You should write it as this:

int min_cost = 99999;
cost[0] = 0;
for (int j = 0; j < no_of_denominations; j++)
{
    if ( (i >= denominations[j]) && (min_cost > cost[i - denominations[j]]) )
    {
        min_cost = cost [i - denominations[j]];
    }
}

At least I find it easier to read. Way easier!

Other than that, it seems pretty much day and night, comparing to the old code.