1. 題目

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

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

示例 1： 輸入： [1,2,3,1] 輸出： 4 解釋： 選擇 1 號預(yù)約和 3 號預(yù)約，總時長 = 1 + 3 = 4。示例 2： 輸入： [2,7,9,3,1] 輸出： 12 解釋： 選擇 1 號預(yù)約、 3 號預(yù)約和 5 號預(yù)約，總時長 = 2 + 9 + 1 = 12。示例 3： 輸入： [2,1,4,5,3,1,1,3] 輸出： 12 解釋： 選擇 1 號預(yù)約、 3 號預(yù)約、 5 號預(yù)約和 8 號預(yù)約，總時長 = 2 + 4 + 3 + 3 = 12。

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/the-masseuse-lcci
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

2. 解題

• dp[i] 表示第 i 次預(yù)約的 最長時間
• 第 i 次預(yù)約，那么可以 + dp[i-2]
• 第 i 次不預(yù)約，可以直接取 dp[i-1]
• 所以轉(zhuǎn)態(tài)轉(zhuǎn)移方程：$dp[i]=\max (dp[i?2]+nums[i],dp[i?1])$

類似題目：
LeetCode 198. 打家劫舍（DP）
LeetCode 213. 打家劫舍 II（DP）
LeetCode 337. 打家劫舍 III（記憶化+遞歸）

class Solution { public:int massage(vector<int>& nums) {int i, n = nums.size();if(n == 0) return 0;if(n == 1) return nums[0];int dp[n] = {0};dp[0] = nums[0];dp[1] = max(nums[0],nums[1]);for(i = 2; i < n; i++){dp[i] = max(dp[i-2]+nums[i], dp[i-1]);}return dp[n-1];} };

總結(jié)

以上是生活随笔為你收集整理的程序员面试金典 - 面试题 17.16. 理发师（动态规划DP）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。