讓我們以問題LeetCode 322 為例。 Coin Change
我知道最好使用動態編程來解決它，但我想專注于我的蠻力解決方案：
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
curr_min = float('inf')
def helper(amount):
nonlocal curr_min
if amount < 0:
return float('inf')
if amount == 0:
return 0
for coin in coins:
curr_min = min(curr_min, helper(amount-coin) 1)
return curr_min
ans = helper(amount)
return -1 if ans == float('inf') else ans
遞回樹看起來像：遞回樹
我可以說它是分而治之：我們將問題分成更小的子問題，單獨解決并使用這些單獨的結果來構建原始問題的結果。
我也可以說它是回溯：我們正在列舉滿足約束的硬幣頻率的所有組合。
我知道兩者都是通過遞回實作的，但我想知道我的蠻力解決方案屬于哪個范例：分而治之或回溯。
uj5u.com熱心網友回復：
對演算法進行分類的一個復雜之處在于，不同類別的演算法之間沒有明確的、明確定義的界限，不同的人可能會有稍微不同的定義。
例如，一般來說，分治演算法涉及將問題分解為不重疊的子問題。（例如，請參閱合并排序、快速排序、二分搜索、最近的點對等。）從這個意義上說，您的演算法不能很好地映射到分而治之的范式，因為您正在考慮的子問題涉及一些他們解決的子問題的重疊程度。（話又說回來，并非所有分治演算法都具有此屬性。例如，參見 stoogesort。）
類似地，回溯演算法通常（但并非總是）通過做出決定來作業，遞回地搜索以查看在給定該決定的情況下是否存在解決方案，然后如果結果不能導致解決方案，則展開選擇。您的演算法沒有此屬性，因為它會探索所有選項，然后選擇最好的。（當我教授入門編程時，我通常以這種方式對演算法進行分類。但我的同事有時將您正在做的事情描述為回溯！）
我會將您的演算法歸類為不同的窮舉搜索系列。您提出的演算法本質上是通過列舉所有可能的找零方式，然后回傳使用最少硬幣的方式來作業的。詳盡的搜索演算法是通過嘗試所有可能的選項并回傳最佳選項來作業的演算法，我認為這是對您的策略進行分類的最佳方法。
uj5u.com熱心網友回復：
對我來說，這不符合任何一種范式。
對我來說，回溯與達到候選人無法進一步發展的程度有關，但在這里我們將其發展到盡頭，無限，我們不會把它扔掉，我們會在比較中使用它。
分而治之我將劃分為相對較少的候選組（經典示例是兩個，例如二分搜索）。為了分而治之而將遞回中的每條路徑稱為組將失去后者的含義。
uj5u.com熱心網友回復：
最實際的答案是沒關系。最安全的答案遞回。我最好的解釋是它的回溯。
我認為這里的選項是遞回、回溯、分治和動態規劃。
遞回是對回溯、D&C 和 DP 的最通用和封裝。如果它確實具有回溯和 D&C 演算法，那么遞回將是最好的答案，因為它包含兩者。
在 Skiena 的 ADM（第 5.3.1 節）中，它說：
典型的分治演算法將給定的問題分成更小的部分，每個部分的大小為n/b。
這種解釋是不符合的，因為我們將解決方案除以coins每個硬幣的數量是不同的大小。
在 Erickson 的演算法（第 1.6 節）中，它說：
分而治之：
- 將給定的問題實體劃分為完全相同問題的幾個獨立的較小實體。
所以在這種情況下，根據遞回樹，并不總是獨立的（它們重疊）。
留下回溯。Erickson 將“遞回策略”定義為：
回溯演算法嘗試逐步構建計算問題的解決方案，一次一小塊。
這似乎足以適應其下的所有 DP 問題。提供的代碼可以說是在解決方案路徑失敗時回溯。
此外，根據維基百科：
對于背包問題和其他組合優化問題，它通常是最方便的決議技術。
硬幣找零是一個無界背包型別的問題，那么它適合回溯的描述。
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/492033.html
下一篇：查找所有可能的功能組合