动态规划:
class Solution {
public:
int massage(vector<int>& nums)
{
int len = nums.size();
if (len == 0 || len == 1)
return len == 0 ? 0 : nums[0];
int (*dp)[2] = new int[len][2];
//初始值
dp[0][0] = 0;//第一个客户不接
dp[0][1] = nums[0];//第一个客户接
for (int i = 1; i < len; i++)
{
//如果第i个客户不接,那么前面i-1位客户有两种选择:
//1.第i-1位客户未接
//2.第i-1位客户接了
//既然第i位客户没有接,那么当前最大预约总时长由第i-1位客户的接与否的两种不同选择决定
//我们要做的就是从前面两种选择中选择出预约时间最长的一种
dp[i][0]=max(dp[i-1][0],dp[i-1][1]);
//如果第i个客户接了,那么前面第i-1位客户只有一种选择:
//1.第i-1位客户不接
//那么当前预约总时长也只有一种选择,那就是到第i-1位时的最长预约时长加上当前客户的预约时长
dp[i][1] = dp[i - 1][0] + nums[i];
}
//最终我们要计算的是最长预约时长:即当前所有客户都过了一遍后,我们要返回计算完最后一个客户时的dp[i-1]
//但是我们要知道最后一位客户也存在两种状态:
//1.被接 2.不被接
//因此我们最终返回的应该是这两种状态中的最大值
return max(dp[len - 1][0], dp[len-1][1]);
}
};
动态规划的优化:
class Solution {
public:
int massage(vector<int>& nums)
{
int len = nums.size();
if (len == 0 || len == 1)
return len == 0 ? 0 : nums[0];
//初始值:
int dp0 = 0;//第一个客户没接,预约总时长为0
int dp1 = nums[0];//第一个客户接了,预约总时长为第一个客户的预约时长
//注意:这里第一个客户已经被计算过了,循环应该从第二个客户开始
for (int i = 1; i < len; i++)
{
//同样:因为当前客户不接,计算总时长时不需要加上当前客户的预约时长
//而计算到当前客户为止的服务总时长需要加上前面i-1位客户的服务总时长
//又因为前面i-1位客户的服务总时长存在两种状态:没接 接了
//因此计算当前客户服务最长时长需要去前面两者状态的最大值
//注意:如果这里的不保存住i-1位客户没有接客的状态,那么在计算dp1的时候加上的就是当前第i位没有接客的状态
int temp = dp0;//用这个来保存住i-1位客户没有接客时的服务总时长
dp0 = max(dp0, dp1);
//同样这里只有一种选择,即前面第i-1位客户没有接的时候的总时长加上当前客户的总时长
//这里注意:这里的dp0应该记录的是i-1位客户没有接客时的服务总时长
dp1 = temp + nums[i];
}
return max(dp0, dp1);//最后返回最后一位客户接与没接两种状态中的最大值
}
};
使用滚动数组进行优化:
class Solution {
public:
int massage(vector<int>& nums)
{
int len = nums.size();
if (len == 0 || len == 1)
return len == 0 ? 0 : nums[0];
int(*dp)[2] = new int[2][2];
dp[0][0] = 0;
dp[0][1] = nums[0];
for (int i = 1; i < len; i++)
{
dp[i%2][0]=max(dp[(i-1)%2][0],dp[(i-1)%2][1]);
dp[i % 2][1] = dp[(i - 1) % 2][0] + nums[i];
}
return max(dp[(len - 1)%2][0], dp[(len - 1) % 2][1]);
}
};
对上面滚动数组实现再优化:
class Solution {
public:
int massage(vector<int>& nums)
{
int len = nums.size();
if (len == 0 || len == 1)
return len == 0 ? 0 : nums[0];
int* dp = new int[2];
//第二位客户的最长预约时长:第一位客户和第二位客户中服务时长较大者
dp[0] = nums[0];
dp[1] = max(nums[0], nums[1]);
for (int i = 2; i < len; i++)
//在选与不选中,选择一个更优解
//如果当前选了,那么i-1就不能选,既然i-1没选,i-1的服务总时长就等于i-2的服务总时长
//如果当前没选,那么当前最长服务时长就是i-1的服务时长
dp[i & 1] = max(dp[(i - 2) & 1] + nums[i], dp[(i - 1)&1]);
return dp[(len-1)&1];
}
};
总结: