algorithm - 找到总和为特定值的所有子集。递归还是DP？

Question

找到总和为特定值的所有子集。

给定一组数字:{1, 3, 9, 12} 和目标值 = 12。找到总和为目标值的不同子集。

答案:[3,9]、[12]。

The problem has been asked here.

显然有两种方法可以解决这类问题。递归或DP。 问题:您如何权衡这两种方法？

我的解决方案:DP 更难，但它消耗的内存更少。在递归中，您必须多次递归调用该函数，这会引入函数开销。但它“相当”容易，但会消耗更多内存。

大家怎么看？

Answer 1

我猜 DP 可以根据方法(自上而下或自下而上)用递归或迭代来实现。通用递归解决方案和 DP 之间的主要区别在于是否使用额外的内存，这将是算法运行时间的权衡。从根本上说，您通过存储和引用它来避免额外的计算。

对于通用递归或 DP 的问题，将在 DP 中使用的内存 与通用递归中的运行时 之间进行权衡。

要考虑的另一件事是并非所有问题都符合 DP 方法。正在考虑的问题具有以下属性

1. “最优子结构”——给定问题的最优解可以通过使用其子问题的最优解来获得。
2. “重叠子问题”- 多次使用相同子问题的解决方案。

上述 2 个属性是 DP 实现所必需的。否则 DP 不会给你任何优化。

例如: 大多数分治法都没有“重叠子问题”属性。二进制搜索没有。

希望对您有所帮助!