分割和征服与回溯
让我们以示例为例
。使用动态编程，但我想专注于我的蛮力解决方案：
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
我可以说这是分裂和征服：我们将问题分为较小的子问题，单独解决并使用这些单独的结果来为原始问题构建结果。
我也可以说这是在回溯：我们正在列举满足约束的所有硬币频率的组合。
我知道两者都是通过递归实施的，但是我想知道我的蛮力解决方案属于哪种范式：分割，征服或回溯。
Let’s use as an example the problem LeetCode 322. Coin Change
I know it is best solved by using Dynamic Programming, but I want to focus on my Brute Force solution:
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
The Recursion Tree looks like: Recursion Tree
I can say it is Divide and Conquer: We are dividing the problem into smaller sub-problems, solving individually and using those individual results to construct the result for the original problem.
I can also say it is Backtracking: we are enumerating all combinations of coin frequencies which satisfy the constraints.
I know both are implemented via Recursion, but I would like to know which paradigm my Brute Force solution belongs to: Divide and Conquer or Backtracking.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
对您的算法进行分类的一个并发症是，不同类别的算法和不同的人之间的界限并不清楚，定义明确的边界可能会考虑到略有不同的定义。
例如，一般来说，，划分和争议算法涉及将问题分开为非重叠的子问题。 （例如，请参见Mergesort，QuickSort，二进制搜索，最接近的点等等。）从这个意义上讲，您的算法不能很好地映射到分界线和争议范式上，因为您正在考虑的子问题涉及一些涉及的子问题他们解决的子问题的重叠程度。 再说一次，并非所有划分算法都具有此属性。
（ 该决定，如果事实证明不导致解决方案，请放松选择。您的算法没有此属性，因为它探讨了所有选项，然后采取最佳状态。 （当我教授介绍编程时，我通常会以这种方式对算法进行分类。但是我的同事有时将您的工作描述为回溯！）
我会将您的算法分类为属于详尽搜索的不同家族。您提出的算法实质上是通过列举所有可能进行更改的方法，然后返回使用最少硬币的算法来起作用的。详尽的搜索算法是通过尝试所有可能的选项并返回最好的方法来起作用的算法，我认为这是对策略进行分类的最佳方法。
A complication in categorizing your algorithm is that there aren’t clear, well-defined boundaries between different classes of algorithms and different people might have slightly different definitions in mind.
For example, generally speaking, divide-and-conquer algorithms involve breaking the problem apart into non-overlapping subproblems. (See, for example, mergesort, quicksort, binary search, closest pair of points, etc.) In that sense, your algorithm doesn’t nicely map onto the divide-and-conquer paradigm, since the subproblems you’re considering involve some degree of overlap in the subproblems they solve. (Then again, not all divide-and-conquer algorithms have this property. See, for example, stoogesort.)
Similarly, backtracking algorithms usually, but not always, work by committing to a decision, recursively searching to see whether a solution exists given that decision, then unwinding the choice if it turns out not to lead to a solution. Your algorithm doesn’t have this property, since it explores all options and then takes the best. (When I teach intro programming, I usually classify algorithms this way. But my colleagues sometimes describe what you’re doing as backtracking!)
I would classify your algorithm as belonging to a different family of exhaustive search. The algorithm you’ve proposed essentially works by enumerating all possible ways of making change, then returning the one that uses the fewest coins. Exhaustive search algorithms are ones that work by trying all possible options and returning the best, and I think that’s the best way of classifying your strategy.
对我来说，这都不适合任何一个范式。
向我进行回溯与达到无法进一步开发候选人的地步有关，但是在这里我们将其开发至无限，而我们不会丢弃，我们将其用于比较。
分割并征服了我将一个部门与相对少数候选人组相关联（经典的例子是两个，例如二进制搜索）。为了分裂和征服，将递归中的每条路径称为群体，将失去后者的含义。
To me this doesn't fit with either paradigm.
Backtracking to me is associated with reaching a point where the candidate cannot be further developed, but here we develop it to it's end, infinity, and we don't throw it away, we use it in comparisons.
Divide and conquer I associate with a division into a relatively small number of candidate groups (the classic example is two, like binary search). To call each path in a recursion a group for the sake of Divide and Conquer would lose the latter's meaning.
最实用的答案是无关紧要。
最安全的答案递归。我最好的解释是它的回溯。
我认为这里的选项是 recursion ， backtracking ， divide and-conquer 和 动态编程。
递归是回溯，d＆amp; c和dp的最通用和封装。如果确实具有回溯和d＆amp; c算法，那么递归将是最好的答案，因为它都包含两者。
在Skiena的ADM（第5.3.1节）中，它说：
通过这种解释，我们将解决方案除以
硬币，而每个硬币量的大小都不同。在埃里克森的算法（第1.6节）中，它说：
因此，在这种情况下，根据递归树，并非总是独立的（它们重叠）。
留下回溯。埃里克森将“递归策略”定义为：
这似乎足以适应其下的所有DP问题。当解决方案路径失败时，可以说提供的代码回溯。
此外，根据 wikipedia ：
硬币更改是一个无界的背包类型问题，然后适合回溯的描述。
The most practical answer is it doesn't matter.
Safest answer recursion. My best interpretation is that its backtracking.
I think the options here are recursion, backtracking, divide-and-conquer, and dynamic programming.
Recursion being the most general and encapsulating of backtracking, D&C, and DP. If indeed it has backtracking and D&C algorithms then recursion would be the best answer as it contains both.
In Skiena's ADM (Section 5.3.1), it says:
By this interpretation is doesn't meet the as we divide our solution by
coinsand each coin amount being a different size.In Erickson's Algorithms (section 1.6), it says:
So in this case, according to the recursion tree, are not always independent (they overlap).
Which leaves backtracking. Erickson defines the 'recursive strategy' as:
Which seems general enough to fit all DP problems under it. The provided code can be said it backtracks when a solution path fails.
Additionally, according to Wikipedia:
Coin Change being an Unbounded Knapsack type problem, then it fits into the description of backtracking.