Recursive and Iterative DP solution using c#


  • 0
    J
    // 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];
    }

Log in to reply
 

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