难度

  • 简单
  • 中等
  • 困难

    标签

    动态规划

    题目描述

    一个有名的按摩师会收到源源不断的预约请求，每个预约都可以选择接或不接。在每次预约服务之间要有休息时间，因此她不能接受相邻的预约。给定一个预约请求序列，替按摩师找到最优的预约集合（总预约时间最长），返回总的分钟数。

注意：本题相对原题稍作改动

示例1：

  1. 输入： [1,2,3,1]
  2. 输出： 4
  3. 解释： 选择 1 号预约和 3 号预约，总时长 = 1 + 3 = 4。

实例2：

  1. 输入： [2,7,9,3,1]
  2. 输出： 12
  3. 解释： 选择 1 号预约、 3 号预约和 5 号预约，总时长 = 2 + 9 + 1 = 12。

题解

  1. class Solution {
  2.     public int massage(int[] nums) {
  3.         int length = nums.length;
  4.         if(length == 0) {
  5.             return 0;
  6.         }
  7.         if(length == 1) {
  8.             return nums[0];
  9.         }
  11.         int[] dp = new int[length];
  12.         dp[0] = nums[0];
  13.         dp[1] = Math.max(dp[0], nums[1]);
  15.         for(int i = 2; i < length; i++){
  16.             dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
  17.         }
  18.         return dp[length - 1];
  19.     }
  20. }