2022年3月25日
dp第三天
「动态规划」 – 学习计划 – 力扣（LeetCode）全球极客挚爱的技术成长平台 (leetcode-cn.com)
这一题，公式不难，直接推到出来了，但是初始化dp[0]，dp[1]的时候，一开始错了，做个记录
/**
198. 打家劫舍
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
示例 1：
输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。
示例 2：
输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
偷窃到的最高金额 = 2 + 9 + 1 = 12 。
提示：
1 <= nums.length <= 100
0 <= nums[i] <= 400
* @author zeroheart
*
*/
public class Question198 {
public static int rob(int[] nums) {
if(nums.length == 0) return 0;
if(nums.length == 1) return nums[1];
// dp[i] 如果是的最大金额，那么dp[i] = Math.max(dp[i-1], dp[i-2]+nums[i])
int[] dp = new int[nums.length];
// 一开始这里初始化有问题，返回的是dp[nums.length];
// dp[0] = 0;
// dp[1] = nums[0];
dp[0] = nums[0];
dp[1] = Math.max(nums[0],nums[1]);
for(int i = 2; i<nums.length; i++){
dp[i] = Math.max(dp[i-1], dp[i-2]+nums[i]);
}
return dp[nums.length-1];
}
public static void main(String[] args) {
// System.out.println(rob(new int[]{1,2,3,1}));
System.out.println(rob(new int[]{2,7,9,3,1}));
}
}
/**
213. 打家劫舍 II
你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。
示例 1：
输入：nums = [2,3,2]
输出：3
解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。
示例 2：
输入：nums = [1,2,3,1]
输出：4
解释：你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。
偷窃到的最高金额 = 1 + 3 = 4 。
示例 3：
输入：nums = [1,2,3]
输出：3
提示：
1 <= nums.length <= 100
0 <= nums[i] <= 1000
* @author zeroheart
*
*/
public class Question213 {
public int rob(int[] nums) {
// 和第一题的区别是首尾相连的
// 思路是0 - n-1算一次，1 - n算一次，看哪个更大。。。
int len = nums.length;
if(len == 0){
return 0;
}
if(len == 1){
return nums[0];
}
if(len == 2){
return Math.max(nums[0],nums[1]);
}
if(len == 3){
return Math.max(Math.max(nums[0], nums[1]), nums[2]);
}
int[] dp1 = new int[len-1];
int[] dp2 = new int[len-1];
dp1[0] = nums[0];
dp1[1] = Math.max(nums[0],nums[1]);
for(int i = 2; i < len-1; i++){
dp1[i] = Math.max(dp1[i-1],dp1[i-2]+nums[i]);
}
dp2[0] = nums[1];
dp2[1] = Math.max(nums[1],nums[2]);
for(int i = 2; i < len-1; i++){
dp2[i] = Math.max(dp2[i-1],dp2[i-2]+nums[i+1]);
}
return Math.max(dp1[len-2], dp2[len-2]);
}
}
首尾成环的时候，需要注意的是可以分成两条链[0, n-1],[1, n]来处理，然后在比较大小。
这题是打家劫舍的变种。。。。。
// nums = [2,2,3,3,3,4] // 这题需要一个转化，定义数组arr[]，存放每个点数的和，arr[0] = 0, arr[1] = 0, arr[2] = 4, arr[3] = 9, arr[4] = 4 // 由于取到nums[i]之后，要删除nums[i] + 1 和 nums[i] - 1的，在新的数组里面，相当于不能取相邻的值，打家劫舍。。。。。
/**
740. 删除并获得点数
给你一个整数数组 nums ，你可以对它进行一些操作。
每次操作中，选择任意一个 nums[i] ，删除它并获得 nums[i] 的点数。之后，你必须删除 所有 等于 nums[i] - 1 和 nums[i] + 1 的元素。
开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。
示例 1：
输入：nums = [3,4,2]
输出：6
解释：
删除 4 获得 4 个点数，因此 3 也被删除。
之后，删除 2 获得 2 个点数。总共获得 6 个点数。
示例 2：
输入：nums = [2,2,3,3,3,4]
输出：9
解释：
删除 3 获得 3 个点数，接着要删除两个 2 和 4 。
之后，再次删除 3 获得 3 个点数，再次删除 3 获得 3 个点数。
总共获得 9 个点数。
提示：
1 <= nums.length <= 2 * 10^4
1 <= nums[i] <= 10^4
* @author zeroheart
*
*/
public class Question740 {
public int deleteAndEarn(int[] nums) {
// nums = [2,2,3,3,3,4]
// 这题需要一个转化，定义数组arr[]，存放每个点数的和，arr[0] = 0, arr[1] = 0, arr[2] = 4, arr[3] = 9, arr[4] = 4
// 由于取到nums[i]之后，要删除nums[i] + 1 和 nums[i] - 1的，在新的数组里面，相当于不能取相邻的值，打家劫舍。。。。。
// 1 <= nums[i] <= 10^4
int[] trans = new int[10001];
for(int i = 0; i<nums.length; i++){
trans[nums[i]] += nums[i];
}
if(trans.length == 0) return 0;
if(trans.length == 1) return trans[0];
if(trans.length == 2) return Math.max(trans[0], trans[1]);
int[] dp = new int[trans.length];
dp[0] = trans[0];
dp[1] = Math.max(trans[0], trans[1]);
for(int i = 2; i<trans.length; i++){
dp[i] = Math.max(dp[i-1], dp[i-2] + trans[i]);
}
return dp[trans.length - 1];
}
}