題目：按摩師
一個有名的按摩師會收到源源不斷的預約請求，每個預約都可以選擇接或不接，在每次預約服務之間要有休息時間，因此她不能接受相鄰的預約，給定一個預約請求序列，替按摩師找到最優的預約集合（總預約時間最長），回傳總的分鐘數，
注意：本題相對原題稍作改動
示例 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，
動態規劃問題：
設定dp[i]陣串列示考慮第i號預約時候的最大預約時間，
得出狀態轉移方程：dp[i] = max{ dp[i-1], dp[i-2]+nums[i] };
上代碼(c)：
int max( int a, int b ) { return a>b?a:b; } int massage(int* nums, int numsSize){ if( numsSize == 0 ) return 0; if( numsSize == 1 ) return nums[0]; int dp[numsSize]; dp[0] = nums[0]; dp[1] = max( nums[0], nums[1] ); for( int i = 2; i < numsSize; i++ ) { dp[i] = max( dp[i-1], dp[i-2]+nums[i] ); } return dp[numsSize-1]; }
2020-03-24-11:12:57
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/40812.html
標籤：C