动态规划的硬币找零问题

Question

这是我关于硬币找零问题的代码，用于打印一组硬币的总路径数和目标金额

def coin_change(coins,amount):
    table=[0 for k in range(amount+1)]
    table[0]=1
    for coin in coins:
        for x in range(coin,amount+1):
            table[x] = table[x]+ table[x-coin]
        print(table)  

    return table[amount]

我想知道是否有任何方法可以使用相同的动态规划解决方案打印这些方式（借助内部构造 table 或任何其他方法）

例如，如果一组硬币是 [1,3,5] 并且目标数量是 6 所以总共有4种可能的方式。 [[1,1,1,1,1,1,],[1,1,1,3],[3,3],[1,5]] 我想要这种方式的列表作为输出。

Answer 1

根据您的要求编辑的答案：

def combine(parent, me):
    if len(parent) == 0:
        return [[me]]
    new_list = []
    for entry in parent:
        new_list.append(entry + [me])
    return new_list


def get_ways(amount, coins):
    table = [0 for k in range(amount + 1)]
    table[0] = 1
    ways = [[] for _ in range(amount + 1)]
    for coin in coins:
        for x in range(coin, amount + 1):
            table[x] = table[x] + table[x - coin]
            ways[x].extend(combine(ways[x - coin], coin))
    print(ways[amount])
    return table[amount]


print(get_ways(6, [1, 3, 5]))

输出：

[[1, 1, 1, 1, 1, 1], [1, 1, 1, 3], [3, 3], [1, 5]]
4

Answer 2

您可以轻松调整当前代码以生成列表解决方案。

def coin_change(coins,amount):
    table=[[] for k in range(amount+1)]
    table[0].append([]) # or table[0] = [[]], if you prefer
    for coin in coins:
        for x in range(coin,amount+1):
            table[x].extend(solution + [coin] for solution in table[x-coin])
        print(table)  

    return table[amount]

table 变量现在是列表列表的列表，内部列表是加起来等于给定值的硬币组合，而不仅仅是这些组合中有多少个的计数是。我没有添加新组合，而是使用我们传递给 extend.

的生成器表达式

Answer 3

    Arrays.sort(coins);
    int dp[]=new int [amount+1];
    Arrays.fill(dp,amount+1);
    dp[0]=0;
    for(int i=0;i<=amount;i++){
        for(int j=0;j<coins.length;j++){
            
            if(coins[j]<=i){
                
                dp[i]=Math.min(dp[i], 1+dp[i-coins[j]]);
                
            }
            else
                break;
            
        }
        
        
    }
   
    return dp[amount]>amount ? -1: dp[amount];

动态规划的硬币找零问题

Coin Change Problem with Dynamic Programming

python

dynamic-programming

coin-change