找到总和为特定值的所有子集。递归还是DP？
find all subsets that sum to a particular value. Recursion or DP?
找到总和为特定值的所有子集。
给定一组数字：{1, 3, 9, 12} 和目标值 = 12。找到总和为目标值的不同子集。
答案：[3,9]，[12]。
The problem has been asked here.
显然有两种方法可以解决这类问题。递归或DP。 问题：您如何权衡这两种方法？
我的解决方法：DP比较难，但是占用内存少。在递归中，您必须多次递归调用该函数，这会引入函数开销。但是它 "considerably" 更容易但消耗更多内存。
大家怎么看？
一般来说，没有任何类型的缓存的递归会导致指数复杂度的解决方案，而这个问题可以用多项式或线性复杂度来解决。那是因为您多次计算相同的部分问题。 memoization 的递归或迭代解决方案可以通过使用更多内存来降低复杂性。
也就是说，您需要考虑输入的限制。对于更大的输入，指数解决方案通常是无用的，因此您没有太多选择。同时，在大多数情况下使用额外的内存并不是真正的问题，除非你为内存非常有限的系统（如嵌入式系统）开发一些东西。
总而言之，在大多数情况下，您会希望牺牲内存以换取算法的复杂性，但您需要根据具体情况来决定。
我猜DP可以根据方法（自上而下或自下而上）用递归或迭代来实现。
通用递归解决方案和 DP 之间的主要区别在于是否使用额外的内存，这将是算法运行时间的权衡。从根本上说，您通过存储和引用它来避免额外的计算。
对于通用递归或 DP 的问题，将在 DP 中使用的 内存 与通用递归中的 运行时 之间进行权衡。
要考虑的另一件事是并非所有问题都符合 DP 方法。
正在考虑的问题具有以下属性
- 'Optimal Substructure' - 给定问题的最优解可以通过使用其子问题的最优解来获得。
- 'Overlapping Subproblems' - 多次使用相同子问题的解决方案。
上述 2 个属性是 DP 实现所必需的。否则DP不会给你任何优化。
例如：大部分分治法没有'Overlapping Subproblems'属性。二进制搜索没有。
希望对您有所帮助！
找到总和为特定值的所有子集。
给定一组数字：{1, 3, 9, 12} 和目标值 = 12。找到总和为目标值的不同子集。
答案：[3,9]，[12]。
The problem has been asked here.
显然有两种方法可以解决这类问题。递归或DP。 问题：您如何权衡这两种方法？
我的解决方法：DP比较难，但是占用内存少。在递归中，您必须多次递归调用该函数，这会引入函数开销。但是它 "considerably" 更容易但消耗更多内存。
大家怎么看？
一般来说，没有任何类型的缓存的递归会导致指数复杂度的解决方案，而这个问题可以用多项式或线性复杂度来解决。那是因为您多次计算相同的部分问题。 memoization 的递归或迭代解决方案可以通过使用更多内存来降低复杂性。
也就是说，您需要考虑输入的限制。对于更大的输入，指数解决方案通常是无用的，因此您没有太多选择。同时，在大多数情况下使用额外的内存并不是真正的问题，除非你为内存非常有限的系统（如嵌入式系统）开发一些东西。
总而言之，在大多数情况下，您会希望牺牲内存以换取算法的复杂性，但您需要根据具体情况来决定。
我猜DP可以根据方法（自上而下或自下而上）用递归或迭代来实现。 通用递归解决方案和 DP 之间的主要区别在于是否使用额外的内存，这将是算法运行时间的权衡。从根本上说，您通过存储和引用它来避免额外的计算。
对于通用递归或 DP 的问题，将在 DP 中使用的 内存 与通用递归中的 运行时 之间进行权衡。
要考虑的另一件事是并非所有问题都符合 DP 方法。 正在考虑的问题具有以下属性
- 'Optimal Substructure' - 给定问题的最优解可以通过使用其子问题的最优解来获得。
- 'Overlapping Subproblems' - 多次使用相同子问题的解决方案。
上述 2 个属性是 DP 实现所必需的。否则DP不会给你任何优化。
例如：大部分分治法没有'Overlapping Subproblems'属性。二进制搜索没有。
希望对您有所帮助！