Python 硬币变化动态规划

Question

我目前正尝试在 Python 中实现动态规划，但我不知道如何设置回溯部分，使其不重复排列。例如，输入为 (6, [1,5])，预期输出应为 2，因为有 2 种可能的方式排列 1 和 5，使它们的总和等于 6。这些组合是 {1,1 ,1,1,1,1} 和 {1,5} 但我的程序目前的工作方式，它考虑了上面显示的组合和组合 {5,1}。这导致输出为 3，这不是我想要的。所以我的问题是"How do I prevent from repeating permutations?"。我当前的代码如下所示。

    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即可。然后始终使用硬币数组中 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):

Answer 2

避免排列的方法之一是按 "non-decreasing" 顺序使用数字。通过这样做，您将永远不会添加 [5 1] 的答案，因为它不在 "non-decreasing" order.And [1 5] 将按 "non-decreasing" 顺序添加。

因此，如果您固定使用排序顺序中的第 i 个数字，那么您的代码将发生变化，而您将永远不会使用严格低于此的数字。

代码更改将如答案中所述，初始数字列表已排序。

Python 硬币变化动态规划

Python Coin Change Dynamic Programming

python

dynamic-programming

coin-change