阅读量:0
1.按摩师（打家劫舍 I）
题目连接：面试题 17.16. 按摩师
一个有名的按摩师会收到源源不断的预约请求，每个预约都可以选择接或不接。在每次预约服务之间要有休息时间，因此她不能接受相邻的预约。给定一个预约请求序列，替按摩师找到最优的预约集合（总预约时间最长），返回总的分钟数。
注意：本题相对原题稍作改动
1.1.题目解析
按摩师可以任意选择预约接还是不接，说明不一定能是从第一个开始。在每次预约服务之间要有休息时间，只要是不相邻即可！那有两个问题，从那个地方开始接？服务完之后，一次跳过多少个预约？
1.2.解决问题
(1)、状态表示
假设以某个位置未结尾或者某个位置未起始 ，定义一个dp[i]就可以表示找到最优的预约集合。这里定义状态表示，以第i个位置为结尾，表示此时，dp[i]表示了预约时间最长！
但是这里有一个问题，第i个位置选还是不选的问题。假设nums = [1 2]，如果i为2，这个位置选还是不选？这里的问题在于不能相邻，那要看第1个位置！所以划分两种情况：
g[i]表示，此时第i个位置必选，此时为最长预约时间
f [i]表示，此时第i个位置不选，此时为最长预约时间
(2)、状态转移⽅程
(3)、初始化
g[0] = nums[0]，f[0] = 0
(4)、初始化顺序
这里根据题目要求，根据状态转移方程，从左往右，将两个dp填充。
(5)、返回值
返回max(f[i],g[i])，即为结果
1.3.参考代码
C++版本：
class Solution { public: int massage(vector<int>& nums) { if(nums.empty()) return 0; int n = nums.size(); vector<int> f(n); vector<int> g(n); f[0] = nums[0]; for(int i = 1;i<n;i++) { f[i] = g[i -1] + nums[i]; g[i] = max(g[i -1],f[i -1]); } return max(f[n -1],g[n -1]); } }; Java版本：
class Solution { public int massage(int[] nums) { int n = nums.length; if(n == 0) return 0; int g[] = new int[n]; int f[] = new int[n]; g[0] = nums[0]; for(int i = 1;i < n;i++) { g[i] = f[i -1] + nums[i]; f[i] = Math.max(f[i -1],g[i -1]); } return Math.max(f[n-1],g[n-1]); } } 2.打家劫舍 II
题目链接：213. 打家劫舍 II
你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。
2.1.解决问题
这个的问题和上一题唯一不同的点在于，第一个房子的处理。情况一： 如果第一个房屋选，第一个房屋的值加上，从第三个房屋开始，到倒数第二个房屋的最大值。情况二： 如果第一个房屋不选，那么从第二个房屋，到最后一个房屋，退化第一题的解决方案。
2.2.参考代码
C++版本：
class Solution { public: int rob(vector<int>& nums) { int n = nums.size(); return max(nums[0] + rob_(nums,2,n-1),rob_(nums,1,n)); } int rob_(vector<int>& nums,int start,int end) { if(start >= end) return 0; int n = end - start; vector<int> g(n); vector<int> f(n); f[0] = nums[start]; for(int i = 1;i <n;i++) { f[i] = g[i -1] + nums[i + start]; g[i] = max(f[i -1],g[i -1]); } return max(f[n-1],g[n-1]); } }; Java版本：
class Solution { public int rob(int[] nums) { int n = nums.length; return Math.max(nums[0] + rob_(nums,2,n -1),rob_(nums,1,n)); } public int rob_(int[] nums,int start,int end){ if(end - start <= 0) return 0; int n = end - start; int f[] = new int[n]; int g[] = new int[n]; f[0] = nums[start]; for(int i = 1;i < n;i++){ f[i] = g[i -1] + nums[start + i]; g[i] = Math.max(f[i -1],g[i - 1]); } return Math.max(f[n -1],g[n -1]); } } 3.删除并获得点数
题目链接：740. 删除并获得点数
给你一个整数数组 nums ，你可以对它进行一些操作。
每次操作中，选择任意一个 nums[i] ，删除它并获得 nums[i] 的点数。之后，你必须删除 所有 等于 nums[i] - 1 和 nums[i] + 1 的元素。
开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数
3.1.解决问题
能不能不删除？当然可以如果在多一步删除操作，岂不是多做无用功。另外，nums数组是无序的，也麻烦，不管三七二十一排序！可以将nums做预处理，映射到一个arr中。
最后映射成arr之后，就又变成的了。对arr数组的i位置的选还是不选，又变成了打家劫舍的问题。
3.2.参考代码
C++版本：
class Solution { public: int deleteAndEarn(vector<int>& nums) { const int N = 10001; vector<int> arr(N); for(auto e : nums) arr[e] += e; vector<int> f(N); vector<int> g(N); for(int i = 1;i < N;i++) { f[i] = g[i -1] + arr[i]; g[i] = max(f[i- 1],g[i -1]); } return max(f[N -1],g[N -1]); } }; 