【dp】Leetcode面试题 17.16. 按摩师

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

暴力法：对于每个预约都有可选和可不选的两种情况

记忆型递归：暴力法的问题在于有很多重复的子问题，可以使用记忆型递归的方式大大提高效率

动态规划：
dp数组的含义：dp[x]代表在[0…x]范围内能取到的最长预约时间

class Solution {

    public int massage(int[] nums) {
        int n = nums.length;
        if (n == 0) return 0;
        if (n == 1) return nums[0];
        int[] dp = new int[n];//dp[x]代表 考虑选择[0 .... x ]范围里的预约 的最大总预约时间
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        for (int i = 2; i < n; i++) {
         //遍历迄今为止的最大值，两种情况取较大：
            //1：预约本次，则上一次不预约（dp[i-2] + nums[i]）
            //2：本次不预约，则值为预约到上一次的最大值
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
        }
        return dp[n - 1];
    }


    public static void main(String[] args) {
        System.out.println(new Solution().massage(new int[]{1, 3, 5, 6, 2, 5}));
    }
}

这一题和leetcode 打家劫舍一摸一样的