文章目录
- 1. 按摩师（面试题 17.16）
- 2. 打家劫舍 II（213）
- 3. 删除并获得点数（740）
- 4. 粉刷房子（LCR 091）
1. 按摩师（面试题 17.16）
题目描述：
状态表示：
设定两个数组，一个数组f[i]代表在i位置接受预约的时长，另一个数组g[i]代表在i位置不接受预约的时长。
状态转移方程：
更新f[i]的值，因为不能连续接收预约，所以f[i]=g[i-1]+nums[i]。更新g[i]=max(f[i-1],g[i-1])，因为如果在i位置不接受预约，i-1位置有接受预约和不接受预约两种情况。
初始化：
避免越界，f数组初始化f[0]=nums[0],g[0]=0。
填表顺序：
从左至右。
返回值：
max(f[n-1],g[n-1])。
代码如下：
class Solution {
public int massage(int[] nums) {
int n = nums.length;
if (n == 0) {
return 0;
}
int[] f = new int[n];
int[] g = new int[n];
f[0] = nums[0];
for (int i = 1; i < n; i++) {
f[i] = g[i - 1] + nums[i];
g[i] = Math.max(g[i - 1], f[i - 1]);
}
return Math.max(g[n - 1], f[n - 1]);
}
}
题目链接
时间复杂度:O(n)
空间复杂度:O(n)
2. 打家劫舍 II（213）
题目描述：
状态表示：
这一题思想和上一题按摩师思想是类似的，因此设定两个数组，一个数组f[i]代表在i位置偷窃达到的最高偷窃价值，另一个数组g[i]代表在i位置不偷窃达到的最高偷窃价值。
状态转移方程：
这里的状态转移方程和上题也是类似的，f[i]=g[i-1]+nums[i]，g[i]=max(f[i-1],g[i-1])，只不过要注意处理首尾连接的情况，大概可以分为两种情况，第一种情况就是在0位置偷窃，那么n-1位置就不能偷窃，第二种情况是在0位置不偷窃。然后分别计算这两种情况搜刮的价值返回最大的即可。
初始化：
这题的初始化和上题一致，根据具体情况避免越界即可。
填表顺序：
都是从左至右。
返回值:
两种情况的最大值，具体可以看代码。
class Solution {
public int rob(int[] nums) {
int n = nums.length;
return Math.max(robChild(nums, 2, n - 2) + nums[0], robChild(nums, 1, n - 1));
}
public int robChild(int[] nums, int start, int end) {
if (start > end) {
return 0;
}
int[] f = new int[end - start + 1];
int[] g = new int[end - start + 1];
f[0] = nums[start];
for (int i = 1; i <= end - start; i++) {
f[i] = g[i - 1] + nums[i + start];
g[i] = Math.max(g[i - 1], f[i - 1]);
}
return Math.max(f[end - start], g[end - start]);
}
}
题目链接
时间复杂度:O(n)
空间复杂度:O(n)
3. 删除并获得点数（740）
题目描述:
状态表示：
这题比较特殊，首先要进行数据预处理，将nums数字的数字存到计数数组count中，如下图。
然后根据count计数数组定义f[i]为删除i位置对应的数字之后能够得到的最大点数，g[i]为不删除i位置对应的数字之后能够得到的最大点数。
状态转移方程：
因为删除数字并且获得点数之后就要删除所有数字±1的相邻的数字，所以f[i]=g[i-1]+count[i]*(i+nums[0])，另外g[i]=max(f[i-1],g[i-1])。
初始化：
为了避免越界要初始化f[0]以及g[0]。
填表顺序：
从左至右。
返回值：
max(f[n-1],g[n-1])。
代码如下:
class Solution {
public int deleteAndEarn(int[] nums) {
Arrays.sort(nums);
int[] count = new int[nums[nums.length - 1] - nums[0] + 1];
for (int i = 0; i < nums.length; i++) {
count[nums[i] - nums[0]] += nums[i];
}
int n = count.length;
int[] f = new int[n];
int[] g = new int[n];
f[0] = count[0];
for (int i = 1; i < n; i++) {
f[i] = g[i - 1] + count[i];
g[i] = Math.max(f[i - 1], g[i - 1]);
}
return Math.max(g[n - 1], f[n - 1]);
}
}
题目链接
时间复杂度:O(n)
空间复杂度:O(n)
4. 粉刷房子（LCR 091）
题目描述：
状态表示：
分别定义三个数组f[i],g[i],h[i]分别代表将i位置的房子粉刷成红色、蓝色或者绿色。
状态转移方程：
因为相邻的房子不能是相同的颜色，并且不同颜色有不同的花费。所以f[i]=min(g[i-1]+cost,h[i-1]+cost)，g[i]=min(f[i-1]+cost,h[i-1]+cost)，h[i]=min(f[i-1]+cost,g[i-1]+cost)。
初始化：
为了避免越界要先初始化f[0]、g[0]、h[0]。
填表顺序：
从左至右。
返回值：
min(f[n-1],g[n-1],h[n-1])。
代码如下：
class Solution {
public int minCost(int[][] costs) {
int n = costs.length;
int[] f = new int[n];
int[] g = new int[n];
int[] h = new int[n];
f[0] = costs[0][0];
g[0] = costs[0][1];
h[0] = costs[0][2];
for (int i = 1; i < n; i++) {
f[i] = Math.min(g[i - 1], h[i - 1]) + costs[i][0];
g[i] = Math.min(f[i - 1], h[i - 1]) + costs[i][1];
h[i] = Math.min(g[i - 1], f[i - 1]) + costs[i][2];
}
return Math.min(f[n - 1], Math.min(g[n - 1], h[n - 1]));
}
}
题目链接
时间复杂度:O(n)
空间复杂度:O(n)
