Python知识分享第二十六天-算法打家劫舍

力扣 198. 打家劫舍

中等
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

def rob(nums):
    if not nums:
        return 0
    elif len(nums) <= 2:
        return max(nums)

    # 动态规划表，dp[i] 表示考虑第 i 个房子时能获得的最大金额
    dp = [0] * len(nums)
    dp[0] = nums[0]
    dp[1] = max(nums[0], nums[1])

    for i in range(2, len(nums)):
        # 在当前位置i，可以选择偷或不偷：
        # - 如果偷，则加上前一个位置之前的最大金额 dp[i-2] + nums[i]
        # - 如果不偷，则保持前一个位置的最大金额 dp[i-1]
        dp[i] = max(dp[i-1], dp[i-2] + nums[i])

    # 最后一个元素保存了最大值
    return dp[-1]

# 示例测试
nums = [1, 2, 3, 1]
print("最大可偷窃金额:", rob(nums))  # 输出应为4 (偷第一个和第三个房子)

这个实现使用了一个数组dp来存储每一个位置上的最大累积金额。对于每个房子，我们有两个选择：要么偷这个房子，那么就不能偷前一个房子；要么不偷这个房子，那么就可以保留到目前为止的最大金额。通过比较这两个选择的结果，我们可以决定哪个选项会带来更大的收益，并更新dp数组中的相应位置。

注意，如果你的问题是指环形排列的房屋（即第一个和最后一个房屋也是相邻的），那么这是一个稍微不同的变种，称为“打家劫舍II”。在这种情况下，需要额外处理首尾相连的情况。

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 个点数。

from collections import Counter
from typing import List

def deleteAndEarn(nums: List[int]) -> int:
    if not nums:
        return 0
    
    # 计算每个数字的总分
    count = Counter(nums)
    # 创建一个数组来表示每个数值的总分
    max_num = max(nums) + 1
    score = [0] * max_num
    for num in count:
        score[num] = num * count[num]
    
    # 动态规划求解
    dp = [0] * max_num
    dp[1] = score[1]
    
    for i in range(2, max_num):
        dp[i] = max(dp[i-1], dp[i-2] + score[i])
    
    return dp[max_num - 1]

# 示例测试
nums = [3, 4, 2]
print("最大可获得点数:", deleteAndEarn(nums))  # 输出应为6 (选择2和4)

在这个解决方案中：

使用Counter来统计每个数字出现的次数，并计算每个数字对应的总分。
创建一个score数组，其中score[i]表示选择数字i所能得到的分数。
定义一个动态规划数组dp，其中dp[i]表示考虑所有小于等于i的数字时可以获得的最大分数。
对于每一个可能的数字i，有两种选择：要么不选择这个数字，那么最大分数就是dp[i-1]；要么选择这个数字，那么最大分数是dp[i-2] + score[i]（因为选择了i就不能再选择i-1了）。
最终结果保存在dp数组的最后一个元素中，即dp[max_num - 1]。
这段代码可以有效地解决问题，并且通过动态规划避免了重复计算，确保了算法的效率。
坚持分享 共同进步

原文地址：https://blog.csdn.net/weixin_45423893/article/details/144461190

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！