我試圖自己解決 LeetCode 問題
這是我的解決方案：
from typing import List
class Solution:
def coinChange(self, nums: List[int], target: int) -> int:
def dfs(remainder):
if remainder<0:
return None
if remainder==0:
return []
shortest_combination=None
for num in nums:
print("target",remainder)
print("num",num)
result=dfs(remainder-num)
if result!=None:
combination=[*result,num]
if shortest_combination==None or len(combination)<len(shortest_combination):
shortest_combination=combination
return shortest_combination
return -1 if dfs(target)==None else len(dfs(target))
s=Solution()
s.coinChange([1,2,5],100)
I print num and remainder, and I see that for some reason remainder never hits 0. Based on DFS, if I keep subtracting 1 from 100 I should be reaching 0, but somehow it does not reach it with any num.
uj5u.com熱心網友回復：
這個問題需要使用動態規劃來解決。給定 any value，假設您已經計算了生成 0, ...value - 1的最小硬幣數量，要計算 的最小硬幣數量value，請查看value - coin1, value - coin2, value - coin3, ...所需的硬幣數量，選擇最小的，并添加一個。
實際上編碼這是你應該自己做的事情。
uj5u.com熱心網友回復：
你的演算法是正確的，它真的沒有命中0，但在這種情況下，你不（列印前函式退出）列印。添加更多除錯，您會看到它確實達到了基本情況和回溯并正確識別子解決方案。
問題實際上是您使用 DFS 訪問的樹呈指數級大，因此您可以多次解決同一問題。如果你添加幾行代碼來實作記憶，你會看到它完成了這項作業：
from typing import List
class Solution:
def coinChange(self, nums: List[int], target: int) -> int:
memo = {} # used for memoization
def dfs(remainder):
if remainder in memo: # already solved this problem?
return memo[remainder] # then return what we got last time
if remainder<0:
return None
if remainder==0:
return []
shortest_combination=None
for num in nums:
result = dfs(remainder-num)
if result!=None:
combination=[*result,num]
if shortest_combination==None or len(combination)<len(shortest_combination):
shortest_combination=combination
memo[remainder] = shortest_combination # memoize this solution
return shortest_combination
return -1 if dfs(target)==None else len(dfs(target))
s=Solution()
print(s.coinChange([1,2,5],100)) # 20
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/313563.html
標籤：python algorithm depth-first-search knapsack-problem coin-change
上一篇：如果我輸出“true”否則“false”，如何檢查（checkV）二叉搜索樹中是否存在值
下一篇：演算法-如何找到最高的人塔的高度