Python硬币变化动态编程

Question

我目前正在尝试用Python实现动态编程，但我不知道如何设置回溯部分，使其不会重复排列。例如，一个输入应该是（6，[1,5]），预期的输出应该是2，因为有两种可能的方式来排列1和5，使它们的总和等于6。这些组合是{1,1,1,1,1}和{1,5}但是我的程序目前的工作方式，它考虑了上面显示的组合和组合{5,1}。这导致输出为3，这不是我想要的。所以我的问题是“如何防止重复排列？”。我当前的代码如下所示。

    import collections as c

    class DynamicProgram(object):
        def __init__(self):
            self.fib_memo = {}
            # nested dictionary, collections.defaultdict works better than a regular nested dictionary
            self.coin_change_memo = c.defaultdict(dict)
            self.__dict__.update({x:k for x, k in locals().items() if x != 'self'})
        def coin_change(self, n, coin_array):
            # check cache
            if n in self.coin_change_memo:
                if len(coin_array) in self.coin_change_memo[n]:
            return [n][len(coin_array)]

            # base cases
            if n < 0: return 0
            elif n == 1 or n == 0: return 1

            result = 0
            i = 0

            # backtracking (the backbone of how this function works)
            while i <= n and i < len(coin_array):
                result += self.coin_change(n-coin_array[i], coin_array)
                i += 1

            # append to cache
            self.coin_change_memo[n][len(coin_array)] = result

            # return result
            return result

Answer 1

快速解决方案是：

result += self.coin_change(n-coin_array[i], coin_array[i:]) # notice coin_array[i:] instead of coin_array

但您希望避免这种情况，因为每次都将创建一个新列表。

更好的解决办法是：

只需在函数中添加一个参数lastUsedCoinIndex。然后始终使用带有索引的硬币

此外，您还必须更改备忘录状态。您当前正在存储sumn和数组大小（与我提供的快速修复不同，在您提供的实现中数组大小没有变化，因此在那里没有任何用处！！）一起作为备忘录的状态。现在您将有n和lastUsedCoinIndex，一起确定备忘录状态。

编辑：

你的函数看起来像：

def coin_change(self,coin_array,n,lastUsedCoinIndex):

在这里，唯一改变的变量将是n和lastUsedCoinIndex。因此，您也可以修改您的构造函数，使其以coin_array作为输入，然后您将通过self.coin_array访问构造函数初始化的coin_array。那么函数将变得简单：

def coin_change(self,n,lastUsedCoinIndex):

Answer 2

避免排列的方法之一是使用“非递减”顺序的数字。这样做，您将永远不会为[5 1]添加答案，因为它不是“非递减”顺序。[15]将按“非递减”顺序添加。

所以代码中的变化是，如果你按照排序顺序使用第i个数字，那么你永远不会使用严格低于这个数字的数字。

代码更改将如Suparshva的回答所述，并对初始数字列表进行排序。