打家劫舍
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 <= 1000 <= nums[i] <= 400
函数签名：
func rob(nums []int) int分析
动态规划
定义动态规划数组 dp, dp[i] 表示 nums[:i+1] 的结果。对于每个房间，有偷和不偷两种选择，容易发现 dp[i] 可以由 dp[i-1] 和 dp[i-2] 推出：dp[i] = max(dp[i-1], dp[i-2]+nums[i])。
可以用两个变量来做动态规划，不用开辟一个数组，这样节省空间。
func rob(nums []int) int {
use, notUse := math.MinInt32, 0
for _, v := range nums {
use, notUse = notUse+v, max(use, notUse)
}
return max(use, notUse)
}时间复杂度 O(n)， 空间复杂度 O(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 = [0]
输出：0提示：
1 <= nums.length <= 1000 <= nums[i] <= 1000
函数签名同上
分析
实际上可以转化为上边那个问题。第一个和最后一个房子不能同时偷，那么可以分别排除这两个房子中的一个计算下结果，最终取最大值就行。
要注意 nums 长度为 1 的情况。
func rob2(nums []int) int {
if len(nums) == 1 {
return nums[0]
}
return max(rob(nums[1:]), rob(nums[:len(nums)-1]))
}时间复杂度 O(n)， 空间复杂度 O(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^41 <= nums[i] <= 10^4
函数签名：
func deleteAndEarn(nums []int) int分析
可以发现，如果选择了某个元素 x，则数组中其他 x 都应该选，数组中所有 x-1 和 x+1 都不应该选。
这样一来就类似打家劫舍问题了！
题目描述不太严谨，实际题意是：删除一个元素
x后，如果存在x-1和x+1，都要删除，删除x得分x， 而x-1及x+1不得分。
func deleteAndEarn(nums []int) int {
maxVal := 0
for _, v := range nums {
if v > maxVal {
maxVal = v
}
}
sum := make([]int, maxVal+1)
for _, v := range nums {
sum[v] += v
}
return rob(sum)
}时间复杂度 O(n+m)， 空间复杂度 O(m)。其中 n 指数组长度，m 指数组中最大元素，根据题目约束，m 最大为 10^4。
在这个问题约束里这样解决就可以了，如果m 特别大就不太可取了。
下边这个解决方案，复杂度只跟 n相关，解除了m的影响，主要思路是先对数组排序，边遍历边统计 sum。
func deleteAndEarn(nums []int) int {
sort.Ints(nums)
res := 0
sum := make([]int, 0, len(nums))
for i, v := range nums {
if i > 0 && v > nums[i-1] + 1 {
res += rob(sum)
sum = sum[:0]
sum = append(sum, v)
continue
}
if len(sum) > 0 && v == nums[i-1] {
sum[len(sum)-1] += v
} else {
sum = append(sum, v)
}
}
return res + rob(sum)
}时间复杂度 O(nlogn)，主要耗费在排序，后边的遍历并 rob 是线性复杂度； 空间复杂度 O(n)。在 n 比较小的情况下这个解法比较好。