LeetCode动画 | 面试题17.16.按摩师
今天分享一个LeetCode题，题号是面试题17.16，标题是按摩师，题目标签是动态规划。
题目描述
一个有名的按摩师会收到源源不断的预约请求，每个预约都可以选择接或不接。在每次预约服务之间要有休息时间，因此她不能接受相邻的预约。给定一个预约请求序列，替按摩师找到最优的预约集合（总预约时间最长），返回总的分钟数。
注意：本题相对原题稍作改动
示例 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。解题
此题的题目标签是动态规划，动态规划能解决的问题，记忆化搜索也能解决；记忆化搜索能解决的问题，动态规划也能解决。
所以，在不知如何用动态规划解决的时候，可以尝试使用记忆化搜索。
个人觉得，记忆化搜索同时进行两个动作：“记忆化”和“搜索”。何谓记忆化，何谓搜索？
搜索，和深度优先搜索一样，都是遍历的动作，也是递归的动作。
记忆化是指将原问题分解的子问题记忆化，下次再碰到一模一样的问题可以通过“记忆”直接获取这个答案，无需再进行递归这个问题。
那如何搜索，如何记忆化呢？
回到题目描述的示例3，输入示例[2, 1, 4, 5, 3, 1, 1, 3]，把这个输入示例看成一个原问题search[index]，其中index是输入示例的索引下标，从最后一个数开始。
search(index)表示目前最长的预约时间。
题目要求：不能接受相邻的预约，替按摩师找到总预约时间最长的预约集合。
search(index) = search(index-1)
= nums[index] + search(index-2)将输入示例通过不能接受相邻的预约分解成两个子问题，search[index - 1] 和 search[index - 2] + nums[index]。而总预约时间最长的search[index]从这两个子问题中获取最大值。
而search(index)中可解决的最小问题如下图所示：
search(index)结束条件
同时也将所有的search方法记忆化，下次碰到一摸一样的search方法通过“记忆”直接获取答案，如下图：
记忆化
动画：记忆化搜索
视频大小：1.63M
Code：记忆化搜索
class Solution {
private int[] nums;
private int[] memory;
public int massage(int[] nums) {
if (nums == null || nums.length == 0) return 0;
if (nums.length < 2) return nums[0];
if (nums.length < 3) return nums[0] > nums[1] ? nums[0] : nums[1];
this.nums = nums;
memory = new int[nums.length];
for (int i = 0; i < nums.length; i++) {
memory[i] = -1;
}
// 记忆化搜索
return search(nums.length - 1);
}
private int search(int index) {
if (index == 0) return nums[0];
if (index == 1) return nums[0] > nums[1] ? nums[0] : nums[1];
if (memory[index] != -1)
return memory[index];
memory[index] = Math.max(search(index - 1), nums[index] + search(index - 2));
return memory[index];
}
}学习过了记忆化搜索，动态规划会变得非常简单。
动态规划可以直接找到记忆化搜索的最小问题解决办法，然后通过for循环拿到这个问题的答案，也同样会“记忆化”。
程序的具体执行动态看下面动画：
动画：动态规划
视频大小：1.41M
Code：动态规划
class Solution {
private int[] nums;
private int[] memory;
public int massage(int[] nums) {
if (nums == null || nums.length == 0) return 0;
if (nums.length < 2) return nums[0];
if (nums.length < 3) return nums[0] > nums[1] ? nums[0] : nums[1];
this.nums = nums;
memory = new int[nums.length];
for (int i = 0; i < nums.length; i++) {
memory[i] = -1;
}
// 动态规划
return dp(nums.length - 1);
}
private int dp(int index) {
memory[0] = nums[0];
memory[1] = nums[0] > nums[1] ? nums[0] : nums[1];
for (int i = 2; i < nums.length; i++) {
memory[i] = Math.max(memory[i - 1], nums[i] + memory[i - 2]);
}
return memory[index];
}
}腾讯云开发者
