一個有名的按摩師會收到源源不斷的預約請求，每個預約都可以選擇接或不接。在每次預約服務(wù)之間要有休息時間，因此她不能接受相鄰的預約。給定一個預約請求序列，替按摩師找到最優(yōu)的預約集合（總預約時間最長），返回總的分鐘數(shù)。

注意：本題相對原題稍作改動

?

示例 1：

輸入： [1,2,3,1]

輸出： 4

解釋： 選擇 1 號預約和 3 號預約，總時長 = 1 + 3 = 4。

示例 2：

輸入： [2,7,9,3,1]

輸出： 12

解釋： 選擇 1 號預約、 3 號預約和 5 號預約，總時長 = 2 + 9 + 1 = 12。

示例 3：

輸入： [2,1,4,5,3,1,1,3]

輸出： 12

解釋： 選擇 1 號預約、 3 號預約、 5 號預約和 8 號預約，總時長 = 2 + 4 + 3 + 3 = 12。

題目來自力扣：

連接：https://leetcode.cn/problems/the-masseuse-lcci/

這年代，當個按摩師也不容易了。還得會動態(tài)規(guī)劃；

下面是代碼：

相關(guān)企業(yè)

相關(guān)標簽

隱藏提示1

此題有遞歸和遍歷兩種解法，但從遞歸開始可能更容易一些。

隱藏提示2

遞歸解法：每個預約都有兩個選擇（接受預約或拒絕預約）。作為一種蠻力方法，你可以在所有可能性的地方遞歸。但是請注意，如果接收了預約請求i，那么你的遞歸算法應(yīng)該跳過預約請求i + 1。

隱藏提示3

遞歸解法：你可以通過制表法優(yōu)化這種方法。這種方法的運行時間是多少？

隱藏提示4

遞歸解法：記憶法的時間復雜度為O(N)，空間復雜度也為O(N)。

隱藏提示5

迭代法：對遞歸法進一步研究。你可以迭代地實現(xiàn)類似的策略嗎？

隱藏提示6

迭代法：從數(shù)組的末尾開始，然后向后計算可能是最簡單的。

隱藏提示7

迭代法：注意，你永遠不會連續(xù)跳過3個預約。為什么不會？因為你總是可以接受中間的預約。

隱藏提示8

迭代法：如果你選擇i，那么將永遠不會選擇i + 1，但是總會選擇i + 2或i + 3。

隱藏提示9

迭代法：使用一個例子并從后往前計算。你可以很容易地找到子數(shù)組{rn}、{rn-1, rn}和{rn-2, ..., rn}。如何使用這些結(jié)果快速找到{rn-3, ..., rn}的最優(yōu)解？

隱藏提示10

迭代法：如果你預約某一時間段，那就不能預約緊鄰的下一時間段，但可以預約之后的任何時間。因此，optimal(ri, ..., rn) = max(ri + optimal(ri+2, ..., rn)，optimal(ri+1, ..., rn))。你可以通過從后往前迭代來解決這個問題。

隱藏提示11

迭代解法：如果你仔細考慮真正需要的數(shù)據(jù)，應(yīng)該能夠在O(n)時間復雜度和O(1)額外空間復雜

執(zhí)行用時：0 ms, 在所有?Java?提交中擊敗了100.00%的用戶

內(nèi)存消耗：38.5 MB, 在所有?Java?提交中擊敗了98.42%的用戶