本文共 1249 字，大约阅读时间需要 4 分钟。

文章目录

题目描述

本文将详细介绍如何使用动态规划方法解决一个经典问题：给定一系列请求序列，每个请求占用一定的时间，要求在不选择相邻的请求的情况下，找到一个请求序列，使其总预约时间最长。我们将从问题分析、动态规划方法的思路、具体实现代码以及优化思路等方面展开讨论。

方法一：动态规划

思路

使用数组 dp 记录到第i个请求序列为止的最大预约时间。通过对递推关系的分析，可以发现存在以下递推公式：

dp[i] = max(dp[i-1], dp[i-2] + nums[i])

其中，dp[i] 表示截止第i个请求时的最大预约时间。递推关系的意义在于，到达第i个请求时，有两种选择：一种是直接取前一个请求的最大预约时间 dp[i-1]；另一种是选择前前一个请求的最大预约时间 dp[i-2]，然后加上当前请求的时间 nums[i]。因为不能选择相邻的请求，所以需要这样递推。

初始化：

• 当 nums 为空时，最大预约时间为 0；
• 当 nums 长度为 1 时，最大预约时间为 nums[0]；
• 当 nums 长度为 2 时，最大预约时间为 nums[0] 和 nums[1] 中的最大值。

代码

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

代码实现

上述代码实现了动态规划的思路。具体来说，代码首先处理了特殊情况，包括 nums 为空、长度为 1 和长度为 2 的情况。对于长度大于等于 3 的情况，代码初始化了 dp 数组，记录每一步的最大预约时间。然后通过遍历 nums 数组，逐步计算每个位置的最大预约时间，最终返回 dp 数组的最后一个元素，即为最终的最大预约时间。