引言
这篇是动态规划的第二期，一起来学习吧。
题目
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.设计状态
2.写出状态转移方程
3.设定初始状态
4.执行状态转移
5.返回最终的解
根据题意
设计状态 ：用一个dp[]数组代表以n号房间为结尾小偷偷到的最高金额
可知 当偷到n号房间时（相当于以n号房为结尾），由题知：
如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警
所以有两种偷窃方式：
1.当偷n号房时，那么那么第n-1号房间是不能偷的，只能偷n-2号房间
//
2.当偷n-1号房间时，第n号房间和n-2号房间都是不能偷的
可知状态转移方程：dp[n]=max(dp[n-1],dp[n-2]+nums[n])
设定初始状态 :
dp[0]表示的是偷0号房间的最大值，自然只能是nums[0]
//
dp[1]表示的是以1号房间为尾偷取的最大金额，
所以只能是取1号房和0号房间的最大值
接下来就是写代码了：
int max(int a,int b) { return (a>b)?a:b; } int rob(int* nums, int numsSize){ if(numsSize==1) return nums[0] ; //dp数组 int dp[101]; dp[0]=nums[0]; //初始状态 dp[1]=max(dp[0],nums[1]); int Max=max(dp[0],dp[1]); for(int i=2;i<numsSize;i++) { //状态转移方程 dp[i]=max(dp[i-1],dp[i-2]+nums[i]); if(dp[i]>Max) Max=dp[i]; } return Max; }
40. 删除并获得点数
给你一个整数数组 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 * 104 1 <= nums[i] <= 104
链接: 删除并获得点数
这是打家劫舍的一道变种题
由题知，当你获得一个nums[i]的值后，需要删除nums[i]-1,nums[i]+1的值，
那是不是可以想办法，
将nums[i],nums[i]-1,nums[i]+1的值和他们在nums[]数组中出现的次数用一个val[]数组存储起来。
可知， nums[i]和 nums[i] - 1 和 nums[i] + 1 的位置在val[]数组上是相邻的
然后定义一个sum[]数组，sum[i]=val[i]*i
最后，运用打家劫舍的模板，修改一下数组范围，即为本题解。
代码：
int max(int a,int b) { return (a>b)?a:b; } int rob(int* nums, int numsSize){ if(numsSize==1) return nums[0] ; int dp[10001]; dp[0]=nums[0]; dp[1]=max(dp[0],nums[1]); int Max=max(dp[0],dp[1]); for(int i=2;i<numsSize;i++) { dp[i]=max(dp[i-1],dp[i-2]+nums[i]); if(dp[i]>Max) Max=dp[i]; } return Max; } int deleteAndEarn(int* nums, int numsSize){ int val[10001],sum[10001]; memset(val,0,sizeof(val)); for(int i=0;i<numsSize;i++) { val[nums[i]]++; } for(int i=0;i<10001;i++) { sum[i]=val[i]*i; } return rob(sum,10001); }
结语
本期动态规划就到这了
我是Tom-猫
如果觉得有帮助的话，记得
一键三连哦ヾ(≧▽≦*)o。
