2、打家劫舍

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

打家劫舍也是动态规划中一个很经典的问题。对于这个系列我们要关注的点要放在偷或者不偷。

• 偷就是前前家的总和加上当前家的总和 dp[i-2]+nums[i]

• 不偷就是前一家的总和 dp[i-1]

我们获取最大值dp[i] = max(dp[i-1], dp[i-2]+nums[i])

采用动规五部曲进行分析

• 确定dp数组的函数到第i家能获取到的金额总和dp[i]
• 确定dp公式dp[i] = max(dp[i-1], dp[i-2]+nums[i])
• 初始化，0位置为nums[0], 1为这前两家能获取的最大值，其他位置都是由前面推出来的，但是不能覆盖推出来的值，所以用0
• 遍历顺序，公式从左到右，因此从小到大

class Solution:
    def rob(self, nums: List[int]) -> int:
        # dp[i] 到第i家能获取到的金额总和
        # dp[i] = max(dp[i-1], dp[i-2]+nums[i])
        # 打家劫舍的问题关键在于偷或者不偷
        # 偷就是前前家的总和加上当前家的总和 dp[i-2]+nums[i]
        # 不偷就是前一家的总和 dp[i-1]

        if len(nums) == 1:
            return nums[0]
        dp = [0] * len(nums)
        dp[0] = nums[0]
        dp[1] = max(nums[0], nums[1])

        for i in range(2, len(nums)):
            dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])
        print(dp)
        return dp[-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

class Solution:
    def rob(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return nums[0]
        r1 = self.helper(nums[1:])
        r2 = self.helper(nums[: len(nums) - 1])
        return max(r1, r2)

    def helper(self, nums: list):
        n = len(nums)
        if len(nums) == 1:
            return nums[0]
        dp = [0] * n
        dp[0] = nums[0]
        dp[1] = max(nums[0], nums[1])

        for i in range(2, n):
            dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])
        return dp[-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 * 104
• 1 <= nums[i] <= 104

思路：

一开始拿到题目我是有点蒙圈的，我是看完解释才明白的。

由于删除它并获得 nums[i] 的点数。之后，你必须删除 所有 等于 nums[i] - 1 和 nums[i] + 1 的元素。

所以我们可以理解为相邻的两个元素是不可以取得，所以和打家劫舍连续起来。

[2,2,3,3,3,4]我可以生成一个字典{1:0， 2:4，3:9，4:1}我们就是来获取其中最大的元素这个时候就和打家劫舍一模一样了。

dp长度为max_num+1,因为{1:0， 2:4，3:9，4:1}可以表达为{0:0，1:0， 2:4，3:9，4:1}所以长度为max_num+1

其他的就不用解释了

import collections


class Solution:
    def deleteAndEarn(self, nums: List[int]) -> int:
        count = collections.defaultdict(int)
        max_num = 0
        for num in nums:
            count[num] += num
            max_num = max(max_num, num)

        dp = [0] * (max_num + 1)
        dp[1] = count[1]
        for i in range(2, max_num + 1):
            dp[i] = max(dp[i - 1], dp[i - 2] + count[i])
        return dp[-1]

1388. 3n 块披萨

给你一个披萨，它由 3n 块不同大小的部分组成，现在你和你的朋友们需要按照如下规则来分披萨：

• 你挑选 任意 一块披萨。
• Alice 将会挑选你所选择的披萨逆时针方向的下一块披萨。
• Bob 将会挑选你所选择的披萨顺时针方向的下一块披萨。
• 重复上述过程直到没有披萨剩下。

每一块披萨的大小按顺时针方向由循环数组 slices 表示。

请你返回你可以获得的披萨大小总和的最大值。

示例 1：

输入：slices = [1,2,3,4,5,6]
输出：10
解释：选择大小为 4 的披萨，Alice 和 Bob 分别挑选大小为 3 和 5 的披萨。然后你选择大小为 6 的披萨，Alice 和 Bob 分别挑选大小为 2 和 1 的披萨。你获得的披萨总大小为 4 + 6 = 10 。

示例 2：

输入：slices = [8,9,8,6,1,1]
输出：16
解释：两轮都选大小为 8 的披萨。如果你选择大小为 9 的披萨，你的朋友们就会选择大小为 8 的披萨，这种情况下你的总和不是最大的。

提示：

• 1 <= slices.length <= 500
• slices.length % 3 == 0
• 1 <= slices[i] <= 1000

思路：

这种有明确的index,rest直接暴力规划解决，先把它解决出来，然后再想着优化

这道题其实和打家劫舍也是有点像，相邻的元素不能同时取，而且还有环。

我们需要求解的问题可以转化为：在一个长度为 3n 的环形数组中，选择其中 n 个不相邻的数，使得这 n 个数的和最大。

class Solution:
    def maxSizeSlices(self, slices: List[int]) -> int:
        n = len(slices) // 3
        p1 = slices[0:len(slices) - 1]
        p2 = slices[1: len(slices)]
        return max(self.process(p1, 0, n, {}), self.process(p2, 0, n, {}))

    def process(self, nums, index, rest, seen):
        """
        在index未知剩余rest个披萨的情况下可以获得的最多披萨个数
        index:当前披萨的位置
        rest:剩余披萨的个数
        """
        if index >= len(nums) or rest == 0:
            return 0
        if (index, rest) in seen:
            return seen[(index, rest)]
        # 拿当前披萨
        cur_point = nums[index]
        take_point = self.process(nums, index + 2, rest - 1, seen) + cur_point
        skip_point = self.process(nums, index + 1, rest, seen)
        ans = max(take_point, skip_point)
        seen[(index, rest)] = ans
        return ans