CODEWITHSUNDEEP
algorithmdynamic-programming
Rahul
Rahul

Reputation: 1005

Decreasing the size of array in coin change problem?

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.

def DynamicChange(money, coins):
    if money<=0:
        return 0
    arr = [0]*(money+1)
    for m in range(1, money+1):
        arr[m] = 9999999
        for coin in coins:
            if m>= coin:
                if arr[m-coin]+1<arr[m]:
                    arr[m] = arr[m-coin]+1
    
    return arr[money]

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?

Upvotes: 0

Views: 211

Answers (1)

trincot
trincot

Reputation: 350137

Not sure if using a depth-first search algorithm would be acceptable, but when turned into a non-recursive implementation, it uses a list that has the same size as the coins list: each value in that list represents the number of coin selections for a particular denomination:

def dfsChange(money, coins):
    if money <= 0:
        return 0
    coins.sort(reverse = True)
    arr = [0] * len(coins) # per coin: number selected
    coin = 0
    count = 0
    mincount = 9999999
    while True:
        arr[coin] = money // coins[coin]
        money -= arr[coin] * coins[coin]
        count += arr[coin]
        if money == 0 and count < mincount:
            mincount = count
        if count >= mincount or coin == len(coins) - 1:
            # back track
            count -= arr[coin]
            money += arr[coin] * coins[coin]
            coin -= 1
            while coin >= 0 and arr[coin] == 0:
                coin -= 1
            if coin < 0:
                return mincount
            arr[coin] -= 1
            count -= 1
            money += coins[coin]
        coin += 1

Upvotes: 1

Related Questions