我正在解决一个破解编码面试的问题，如下所示：
一位受欢迎的按摩师接连收到一系列预约请求，并在讨论接受哪些。她需要在两次约会之间休息15分钟，因此不能接受任何相邻的请求给定一个连续的预约请求序列（15分钟的所有倍数，不重叠，且不能移动），找到按摩师可以遵守的最佳（总预定分钟数最高）设置。返回分钟数。
实例
输入：{30，15，60，75，45，15，15，45}
输出：180分钟（{30，60，45，45}）
输入：[75，105，120，75，90，135]
输出：[75120135]
我的递归解决方案围绕着以下内容：
取arr[0]，并调用maxval（index+2）与maxval（index+3）
做和我为arr[1]做arr[0]一样的事情。在这两个初始启动之后，算法的其余部分是等价的（即arr[0]和arr[1]的起点的maxval（index+2）和maxval（index+3）
因此，每个元素都可以选择跳过两个或跳过3个。
教科书中的递归解决方案的工作原理如下：
maxval=maxval（索引+2）+arr[index0]与maxval（索引+1）
我的算法在某些方面不正确吗？或者它只是解决问题的一种同样最佳的方法这两种算法不都应该是O（2^N）不带记忆，O（N）带记忆吗？
最佳答案
你的算法是正确的，虽然更复杂。它不考虑没有相邻元素的每一个子集，但不考虑它的最大子集，因此不是最优的，因为约会时间都应该是正的。
给定解的无记忆运行时间是θ（Fib（n）），其中Fib（n）是第n个Fibonacci数（约O（1.62^n））你的复发率是
T(n) = T(n-2) + T(n-3) + T(n-4)
或
T(n) = T(n-2) + 2 T(n-3) + T(n-4)
取决于是否重用maxVal（index+3）的计算前一个实现的运行时间约为o（1.47^n）；后一个实现的运行时间约为o（1.72^n）。
关于algorithm - 将我的算法解决方案与教科书进行比较，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/42080914/