求和为特定值的所有子集。递归还是DP?

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

对于泛型递归或DP问题,将在以下两者之间进行权衡: 用于DP VS 运行时 在泛型递归中。

所考虑的问题具有以下特性

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

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

大多数分治方法不具有“重叠子问题”特性。二进制搜索没有。

希望有帮助!

memoization 可以通过使用更多内存来降低复杂性。

也就是说,您需要考虑您输入的约束。对于较大的输入,指数解通常是无用的,因此您没有太多选择。同时,在大多数情况下,使用额外的内存并不是一个真正的问题,除非您为内存非常有限的系统(如嵌入式系统)开发一些东西。

总而言之,在大多数情况下,您希望在算法复杂性方面权衡内存,但需要根据具体情况来决定。