Minimum number of coins problem using dynamic programming - follow up 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 &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;

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 &lt; no_of_denominations ; j++ )
    {
        if( ( i &gt;= denominations [ j ] ) &amp;&amp; ( min_cost &gt; 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" , &amp;total_cost ) ;

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

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

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

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

int main()
{
    input () ;
    calc_print () ;
    return 0;
}
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 &lt; 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.