返回数组动态编程硬币变更器

问题描述

我正在尝试获得目标金额总和的所有硬币。我弄到了所需数量的硬币。我该如何着手解决它。

您可以无限制地使用相同的硬币 例如。change([2], 10)=>[2, 2, 2, 2, 2]

def change(coins, amount):
    result = [amount+1] * (amount+1)

    result[0] = 0

    for i in range(1, amount+1):
        for coin in coins:
            if i >= coin:
                result[i] = min(result[i], result[i-coin] + 1)

    if result[amount] == amount+1:
        return -1

    return result[amount]

change([1, 2, 5,8], 7)=>[5, 2]顺序不重要。

---

解决方案

如果您使用dyanmic programming只能得到最好的结果，您可以使用一个数组来存储dynamic programming的中间结果，我根据您的DP版本进行了修改：

def change(coins, amount):
    result = [amount+1] * (amount+1)
    coins_results = [[] for _ in range(amount+1)]

    result[0] = 0

    for i in range(1, amount+1):
        for coin in coins:
            if i >= coin and result[i - coin] + 1 < result[i]:
                result[i] = result[i-coin] + 1
                coins_results[i] = coins_results[i-coin] + [coin]

    if result[amount] == amount+1:
        return []

    return coins_results[amount]

测试：

print(change([1, 2, 5, 8], 7))
print(change([2], 10))

输出：

[5, 2]
[2, 2, 2, 2, 2]

---

以下是backtracking输出所有结果的版本：

def change(coins, amount):
    res = []

    def backtrack(end, remain, cur_result):
        if end < 0: return
        if remain == 0:
            res.append(cur_result)
            return
        if remain >= coins[end]:
            backtrack(end, remain - coins[end], cur_result + [coins[end]])
        backtrack(end - 1, remain, cur_result)

    backtrack(len(coins) - 1, amount, [])
    return res

测试：

print(change([1, 2, 5, 8], 7))
print(change([2], 10))

输出：

[[5, 2], [5, 1, 1], [2, 2, 2, 1], [2, 2, 1, 1, 1], [2, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1, 1]]
[[2, 2, 2, 2, 2]]

希望这对您有帮助，如果您有进一步的问题，请发表意见。：)