蟒蛇幣更改動態編程

我目前正試圖在Python中實現動態編程，但我不知道如何設置回溯部分，以便它不重複排列。例如，輸入爲（6，[1,5]），預期的輸出應爲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

來源

2017-09-16 Matthew Anderson

[Memoizing Coin Change]的可能重複（https://stackoverflow.com/questions/20742714/memoizing-coin-change） –

快速修復將是：

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):

來源

2017-09-17 07:30:37 Suparshva

這是否包括在備忘錄中實現一系列可用硬幣？ –

我不明白你的上面的問題......但備忘錄狀態只包含'n'和'lastUsedCoinIndex'作爲變量，隱含地已經提供了關於可用硬幣的信息，因爲給定整個數組，你總可以知道什麼硬幣可用進行計算。這是否清除你的疑惑？ – Suparshva

我做了一些闡述。看看它是否更清楚解釋。 – Suparshva

避免置換的一種方法是以「非遞減」順序使用數字。通過這樣做，您將永遠不會爲[5 1]添加答案，因爲它不是「非遞減」順序。並且[1 5]將按照「非遞減」順序添加。

因此，如果您修改爲按照排序順序使用第i個數字，那麼您的代碼中的更改將永遠不會使用嚴格低於此數的數字。

代碼更改將按照Suparshva's中的描述進行回答，並將初始數字列表排序。

來源

2017-09-17 08:31:28

蟒蛇幣更改動態編程

回答

相關問題