用递归的方式在 Python 中更改硬币/为什么没有工作？

Question

这是我的代码。换硬币的任务。我需要获取列表列表，以及交换选项。

a = []
def coinChange(coins, amount, result=None):
    if result is None: 
        result = []
    
    if amount < 1 and sum(result) == 3:
        return a.append(result)

    else:
        for i in coins:
            if amount - i >= 0:
                result.append(i)
                coinChange(coins, amount - i, result)            
    return 

coinChange([1,2,3], 3)
print(a)

他们return

[1,1,1,2,2,1,3]

但我需要获取列表列表。每个子列表应仅包含加起来为 3 的数字。

例如：

[[1,1,1], [2,1], [3]]

如何获得这样的列表？谢谢

Answer 1

简单的解决方案

代码

def coinChange(coins, amount, result=None, solutions = None):
    '''
        result - stores current set of coins being tries
        soltions - solutions found so far
    '''
    if result is None: 
        result = []
        
    if solutions is None:
        solutions = []

    if amount == 0:
        # Add solution
        solutions.append(result[:])  # append a copy since result will change
    elif amount > 0:
        for i in coins:
            if amount - i >= 0:
                # Adding i to list of coins to try
                coinChange(coins, amount - i, result + [i,], solutions)
                
    return solutions

测试

a = coinChange([1,2,3], 3)
print(a)
            
# Capture the solution in a (i.e. don't make it global--generally bad practice)         
a = coinChange([1,2,3], 3)
print(a)

输出

[[1, 1, 1], [1, 2], [2, 1], [3]]

使用生成器更简单

def coinChange(coins, amount, result=None):
    '''
        result - stores current set of coins being tries
        soltions - solutions found so far
    '''
    if result is None: 
        result = []
        
    if amount == 0:
        # report solution
        yield result
        
    if amount > 0:
        for i in coins:
            yield from coinChange(coins, amount - i, result + [i,])    
            
a = list(coinChange([1,2,3], 3))
print(a)

使用缓存

通过修改 GalSuchetzky 答案最容易说明缓存的使用。

问题

不能直接在 coinChange 函数上使用缓存，因为参数不可哈希（例如，coins 是一个列表，因此不可哈希）
我们通过使用一个嵌套函数（助手）来恢复它，它的参数是可散列的，必要时索引到硬币中

代码

def coinChange(coins, sum_):
    '''
        Inputs:
            coins - list of coins
            sum_  - value coin should sum to (use sum_ since sum is a builtin function)
    '''
    
    def coinChangeHelper(j, total):
        '''
            Uses cache to compute solutions
            
            Need helper function since coins is a list so can't be hashed to placed in cache
            
            Inputs:
                j     - current index into coins
                total - current sum
        '''
        if (j, total) in mem_cache:
            # Use cache value
            return mem_cache[(j, total)]
        
        # Stop condition.
        if total == 0:
            mem_cache[(j, total)] = [[]]
        else:
            # Recursive step
            solutions = []

            for i in range(j, len(coins)):
                if coins[i] <= total:
                    lst = coinChangeHelper(i, total - coins[i])
                    solutions.extend([[coins[i]] + l for l in lst])

            mem_cache[(j, total)] = solutions
        
        return mem_cache[(j, total)]

    # Init cache
    mem_cache = {}
    
    return coinChangeHelper(0, sum_)

print(coinChange([1, 2, 3], 3))

Answer 2

我什至会 DarrylG's 进一步回答并建议不要通过递归堆栈传递结果，因为它会使递归的整个概念复杂化。

简而言之，您通常应该：

假设您可以解决问题的较小版本（这是您正在实现的确切功能）
用小问题的解解决原问题（递归步骤，这里调用函数）
为问题的最简单情况定义显式解决方案，这实际上是递归的停止条件。

下面是使用这些提示解决问题的示例代码：

def coinChange(coins, sum):
    # Stop condition.
    if sum == 0:
        return [[]]

    # Recursive step
    solutions = []
    for i, coin in enumerate(coins):
        if coin <= sum:
            lst = coinChange(coins[i:], sum - coin)
            solutions.extend([[coin] + l for l in lst])

    return solutions


print(coinChange([1, 2, 3], 3))

运行的结果：

[[1, 1, 1], [1, 2], [3]]

检查您是否在没有依赖的情况下执行这些步骤的好测试正在尝试 one-line 您的代码：

def coinChange(coins, sum):
    return [[c] + l for i, c in enumerate(coins) if c <= sum for l in coinChange(coins[i:], sum - c)] if sum > 0 else [[]]

请注意，有时它可能无法读取，因此您可以决定将其保留为 one-line 格式。

用递归的方式在 Python 中更改硬币/为什么没有工作？

Change coins in Python with recursive / Why no work?

python

algorithm

recursion

coin-change