这是我正在努力的问题
我实施了蛮力解决方案和分而治之（递归）解决方案 . 他们都使用这个输入（从第1到第4个）
对于暴力解决方案，我所做的是生成{1,2,3,4}的所有子集，遍历所有子集并仅检查包含1和4的子集 . 我知道我的暴力解决方案将在O（2n）时间，因为有数学上2n个子集，我必须遍历所有这些子集 .
对于我的递归解决方案 . 我所做的是打破这个问题，以便生成/将要检查的唯一解决方案是包含1和4的解决方案 . 例如，从1开始你可以转到2,3,4如果你转到2，你可以去3,4，等等......到达4 .
在分析了这两种算法之后，我意识到唯一的区别是分而治之不会有1和4，但是蛮力会比较{2,3} . 这种差异将如何影响递归算法的时间复杂度 . 递归算法是否也会在O（2n）或更少的情况下运行，因为它会检查更少的子集？
2 回答
递归优化的额外步骤是使用memoization . 推理 - 一旦你得到并停在第x条，它总是相同的成本直到结束，无论你来自哪里 .
事实证明，所有需要的是在索引i最低价格的数组保持结束 . 这可以在O（n²）时间从右到左填充 .
存在一种简单的动态编程解决方案 .
考虑每个连续较长的最佳独木舟旅程作为一些较短的最佳独木舟旅程的功能 . 也就是说，最便宜的方式去旅行4是最便宜的方式去旅行3后加上3到4区间的最佳决定 . 然后考虑最便宜的方式到达后5作为先前计算的最便宜的访问方式的函数发布4 .
在代码中实现这种递归，你的解决方案应该是O（n ^ 2），类似于常年的CLRS最喜欢的：切杆问题：http://www.geeksforgeeks.org/dynamic-programming-set-13-cutting-a-rod/
分而治之的方法将检查启动租赁的单身人士，然后“合并”步骤将优化新的双人/ 4顿/等 . 它会比O（2 ^ n）好得多，因为你不会重新计算每个子路径的所有可能性，但它是一个贪婪的算法 - 它在有完整的答案信息之前对答案做出假设 .
如果您假设在子集的某个合并步骤期间发生了最佳决策，则必然会错过以1为单位租船并在n处返回的情况是最佳解决方案，但运行时为O（n log n） . 但是，如果您检查输入并针对每个合并进行优化，那么您将回到O（2 ^ n） .