algorithm - 在硬币找零问题中减小数组的大小？

Question

硬币找零问题的简单 DP 解决方案使用大小为 SUM 的一维数组，并将其从 0 填充到 SUM。基于重复次数 NUMBER_OF_COINS = min(array[sum-coin1]+1, array[sum-coin2]...)。我写的代码是这样的。

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]

我遇到了一个有趣的问题，即将数组的大小减少到硬币的数量。无法想出相同的解决方案。我们怎样才能将数组的大小减小到硬币的数量并且仍然获得硬币的最小数量？

标签： algorithmdynamic-programming

Answer 1

不确定使用深度优先搜索算法是否可以接受，但是当变成非递归实现时，它使用一个与列表大小相同的coins列表：该列表中的每个值代表一个硬币选择的数量特定面额：

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