Coin Denomination Problem !

I was asked to solve the coin denomination problem in an Interview. The problem statement is: Given an amount of money, and some coins that are used in some country ( which will definitely include at-least 1 coin of worth 1), you have to find the minimum number of coins which will be used to convert the amount of money in coins. I came up with 3 solutions ( greedy algorithm which is trivial ), recursive which is tough but costly and finally a Dynamic Programming solution. I coded the algorithm in C# which is pasted below, this code will print the minimum number of coins that will be used, but the not exactly those coins which are being used in the solution, for that very purpose we have to store some addictional information, but doing that is not that much of a tough task, so enjoy the C# code

//***************** this is portion of code

int money = 9; // set any amount of money here

int [] maxcoins = new int [money + 1];

int [] coins = { 1 , 4 , 5}; // set any values here

for( int i=0; i < maxcoins.Length; i++)
    maxcoins[i] = 10000; //this value should infact be very large

maxcoins[0] = 0;

for(int i = 1; i <= money; i++)
{
    for( int j=0 ; j < coins.Length; j++)
    {
         if( i >= coins[i])
           if( (maxcoins[i - coins[j]] + 1) < maxcoins[i])
             maxcoins[i] =  maxcoins[ i - coins[j]] + 1;
    }
}

Console.WriteLine( maxcoins[money + 1]);

I will explain the logic later.

Haroon