Python硬币变化动态编程

Question

我目前正在尝试在Python中实现动态编程，但我不知道如何设置回溯部分，使其不会重复排列。 例如，输入为 (6， [1,5])，预期输出应为 2，因为有 2 种可能的方法可以排列 1 和 5，以便它们的总和等于 6。这些组合是 {1,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

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

因此，代码中的更改将是，如果您修复以排序顺序使用第 i 个数字，那么您将永远不会使用严格低于此数字的数字。

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

Answer 2

快速解决方法是：

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

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

更好的解决方法是：

只需在函数中添加参数lastUsedCoinIndex即可。然后始终使用硬币数组中带有index>=lastUsedCoinIndex的硬币。这将确保解决方案是不同的。

此外，您还必须更改备忘录状态。您目前正在将总和n和size of array(与我提供的快速修复不同，数组的大小在您提供的实现中没有变化，因此它在那里没有用！！现在您将拥有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):