Recursion gives correct answer for minimum Coin Change but dynamic programming gives wrong answer
<p>I am trying to do this problem for quite a few hours but I can't think intuitively about it. Having sort of a mental block regarding it. After many tries I was able to get recursion solution correct for cases where solution exist. So I have following questions:</p>

<ol>
<li><p>Recursion program is giving correct solution for input in which solution exist. How to return 'No solution exist' where solution doesn't exist. Ex for Coins [3,10], no solution exist for change 17.</p></li>
<li><p>What is the mistake in DP program? I tried using memoization technique where I created a dictionary and added values to it but the program is not working correctly.</p></li>
</ol>



<pre><code>import math
def findMinCoins(denomination, change):
    #recursive solution
    minCoins = change
    if(len(denomination )== 0 or change ==0): #when there are no coins or change is 0
        return 0
    elif(change in denomination):
        return 1
    elif(change &lt; min(denomination)):
        return float("inf")
    else:
        for i in denomination:
            if(i&lt;=change):
                numCoins = 1 + findMinCoins(denomination, change - i)
                if(numCoins &lt; minCoins):
                    minCoins = numCoins
    return minCoins

c = [3,10]
d = 30

print findMinCoins(c,d)
</code></pre>

<p>Now here is DP solution.</p>

<pre><code>import math
coinsDict = {}

def findMinCoins(denomination, change):
    minCoins = change
    if(len(denomination )== 0 or change ==0):
        return 0
    elif(change in denomination):
        return 1
    elif(change &lt; min(denomination)):
        return float("inf")
    else:
        for i in denomination:
            if (coinsDict.get(change)):
                print 'dictionaty',change, coinsDict.get(change)
                return coinsDict[change]
            elif(i&lt;=change):
                numCoins = 1 + findMinCoins(denomination, change - i)
                if(numCoins &lt; minCoins):
                    minCoins = numCoins
                    print change, numCoins
                    coinsDict[change] = numCoins

    return minCoins

c = [3,10]
d = 30

print findMinCoins(c,d)
</code></pre>