# Recursive and Iterative DP solution using c#

• ``````// O(n^c) n:amount, c:coins. This is a Top-Down solution
public int CoinChange(int[] coins, int amount)
{
int[] cachedResults = new int[amount];
return RunRecursion(coins, amount, cachedResults);
}

private int RunRecursion(int[] coins, int amount, int[] cachedResults)
{
if(amount<=0) // Invalid Input
{
return (amount==0)?0:-1;
}
if(cachedResults[amount-1]!=0) // If we already have cached result
{
return cachedResults[amount-1];
}
int min = Int32.MaxValue;
for(int i=0; i<coins.Length; i++)
{
if(amount>coins[i])
{
int temp = RunRecursion(coins, amount-coins[i], cachedResults)+1;
min = (temp>1 && temp<min)?temp:min;
}
else if(amount==coins[i])
{
min = 1;
break;
}
}
min = (min==Int32.MaxValue)?-1:min;
cachedResults[amount-1] = min;
return min;
}
``````

``````// O(n*c) n:amount, c:coins. This is a Bottom-Up solution
public int CoinChange(int[] coins, int amount)
{
if(amount<=0)
{
return (amount==0)?0:-1;
}
int[] cachedResults = new int[amount+1];
for(int i=1; i<=amount; i++)
{
cachedResults[i] = Int32.MaxValue;
for(int j=0; j<coins.Length; j++)
{
if(i>=coins[j] && cachedResults[i-coins[j]]!=-1)
{
cachedResults[i] = Math.Min(cachedResults[i], 1+cachedResults[i-coins[j]]);
}
}
if(cachedResults[i]==Int32.MaxValue)
{
cachedResults[i] = -1;
}
}
return cachedResults[amount];
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.