algorithm - 时间复杂度如何从蛮力变为递归解决方案？

Question

这是我正在处理的问题

我实现了一个强力解决方案和一个分而治之(递归)解决方案。他们都使用这个输入(从帖子 1 到 4)

对于暴力解决方案，我所做的是生成 {1,2,3,4} 的所有子集，遍历所有子集并仅检查包含 1 和 4 的子集。我知道我的暴力解决方案将在 O(2ⁿ) 时间内运行，因为在数学上有 2ⁿ 子集，我必须迭代所有这些。

对于我的递归解决方案。我所做的是分解这个问题，以便生成/将检查的唯一解决方案将是包含 1 和 4 的解决方案。例如，从 1 可以转到 2、3、4，如果转到 2，您可以转到 3、4，依此类推...直到到达 4。

在分析了这两种算法之后，我意识到唯一的区别是分而治之法甚至不会检查没有 1 和 4 的子集，而蛮力法会检查 {2,3}。这种差异将如何影响递归算法的时间复杂度。递归算法是否也会在 O(2ⁿ) 或更短的时间内运行，因为它检查的子集更少？

Answer 1

递归优化的额外步骤是使用内存。推理是这样的——一旦你到达并停在 x 后，无论你来自哪里，到最后都是相同的成本。
事实证明，只需要数组以索引 i 的最低价格持有即可结束。这可以在 O(n²) 时间内从右到左填充。