title: Decreasing the size of array in coin change problem?
body: <p>The simple DP solution of the coin change problem uses a 1D array of size SUM, and fills it from 0 to SUM. Based on the recurrence NUMBER_OF_COINS = min(array[sum-coin1]+1, array[sum-coin2]...).
  The code that i have written is this.</p>
  <pre><code>def DynamicChange(money, coins):
      if money&lt;=0:
          return 0
      arr = [0]*(money+1)
      for m in range(1, money+1):
          arr[m] = 9999999
          for coin in coins:
              if m&gt;= coin:
                  if arr[m-coin]+1&lt;arr[m]:
                      arr[m] = arr[m-coin]+1
      
      return arr[money]
  </code></pre>
  <p>I came across an intriguing question of decreasing the size of the array to number of coins. Couldn't come up with a solution for the same. How can we decrease the size of the array to the number of coins and still get the min number of coins?</p>