杭州哪家公司做网站,郑州关键词排名顾问,重庆市公共资源交易中心网,ipad wordpress 应用你是一个专业的小偷#xff0c;计划偷窃沿街的房屋。每间房内都藏有一定的现金#xff0c;影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统#xff0c;如果两间相邻的房屋在同一晚上被小偷闯入#xff0c;系统会自动报警。
给定一个代表每个房屋存放金额的…你是一个专业的小偷计划偷窃沿街的房屋。每间房内都藏有一定的现金影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统如果两间相邻的房屋在同一晚上被小偷闯入系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组计算你 不触动警报装置的情况下 一夜之内能够偷窃到的最高金额。 示例 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
from typing import Listclass Solution:def rob(self, nums: List[int]) - int:# 如果房屋数量为 0直接返回 0因为没有房子可偷if len(nums) 0:return 0# 如果房屋数量为 1返回唯一一间房屋的金额if len(nums) 1:return nums[0]# 如果房屋数量为 2返回两者中较大的金额if len(nums) 2:return max(nums[0], nums[1])# 创建一个 dp 数组其中 dp[i] 表示偷到第 i 间房屋时能获取的最大金额dp [0] * len(nums)# 初始化前两间房屋的最大偷窃金额dp[0] nums[0] # 第一间房屋只能偷它自己dp[1] max(nums[0], nums[1]) # 第二间房屋可以选择偷第一间或第二间取金额较大者# 从第 3 间房屋开始计算每间房屋的最大偷窃金额for i in range(2, len(nums)):# 对于第 i 间房屋可以选择# 1. 偷它并加上偷第 i-2 间房屋的最大金额因为相邻房屋不能同时偷# 2. 不偷它直接取第 i-1 间房屋的最大金额dp[i] max(dp[i-2] nums[i], dp[i-1])# 返回最后一间房屋对应的最大偷窃金额即为结果return dp[-1]解释 特殊情况处理 如果房屋数量为 0则返回 0因为没有房屋可以偷。如果房屋数量为 1则返回第一个房屋的金额因为只能偷这一间。如果房屋数量为 2则只能偷其中金额较大的一间因此返回这两者中的最大值。 动态规划数组 dp dp[i] 代表到达第 i 间房屋时小偷能偷到的最大金额。初始化 dp[0] 为第一个房屋的金额dp[1] 为前两间房屋中金额较大的值。 动态规划递推 对于每一间房屋从第 3 间开始即下标为 2 的房屋有两种选择 偷这一间房屋加上第 i-2 间房屋的最大金额。不偷这一间房屋取前一间房屋的最大金额。在这两者中选择较大的值更新 dp[i]保证每一步都获得最大金额。 结果返回 dp[-1] 即为偷窃到最后一间房屋时的最大金额也就是最终答案。 dp 是动态规划Dynamic Programming的简称它是一种常见的算法设计思想用来解决具有重叠子问题和最优子结构的问题。动态规划通过将问题分解为更小的子问题记录这些子问题的解然后根据这些子问题的解来构造出原问题的解从而避免重复计算。 在这个小偷问题中dp 是一个数组用来存储每个子问题的最优解具体来说 dp[i] 表示到达第 i 间房屋时能够偷到的最大金额。这个数组记录了在每个房屋时如何做出选择偷还是不偷使得偷窃的总金额最大。 动态规划的关键概念 重叠子问题 动态规划适用于那些可以通过递归或分解为相似的子问题解决的情况。比如在小偷问题中 如果你决定偷第 i 间房屋那么你还需要知道偷第 i-2 间房屋能得到的最大金额因为相邻的房子不能同时偷。如果你不偷第 i 间房屋那么你只需要知道偷第 i-1 间房屋的最大金额。 最优子结构 问题的整体最优解可以由其子问题的最优解构成。在这个问题中偷窃第 i 间房屋的最优解可以通过第 i-2 间房屋和第 i-1 间房屋的最优解推导出来。 举个例子解释 dp 的含义 假设房屋里的金额是 [2, 7, 9, 3, 1]小偷希望能偷到最多的钱但不能偷相邻的房子。 dp[0] 2表示只看第 1 间房屋时最多能偷 2 元。dp[1] 7表示只看前两间房屋时最多能偷 7 元因为第 2 间房屋钱更多偷第 1 间房屋不划算。dp[2] max(dp[0] nums[2], dp[1]) max(2 9, 7) 11表示到第 3 间房屋时可以选择偷第 1 间和第 3 间房屋共 2 9 11 元或者只偷前两间房屋共 7 元所以偷第 1 和第 3 间房屋的总金额最大。dp[3] max(dp[1] nums[3], dp[2]) max(7 3, 11) 11到第 4 间房屋时最优解是保持偷前 3 间房屋的最大金额11 元因为偷第 2 间和第 4 间的金额不比之前多。dp[4] max(dp[2] nums[4], dp[3]) max(11 1, 11) 12到第 5 间房屋时最优解是偷第 1、3、5 间房屋总金额为 12 元。 动态规划公式 dp[i] max(dp[i-2] nums[i], dp[i-1]) 这个公式的意思是对于每一间房屋 i你有两个选择 偷它然后加上两间前房屋i-2的最大偷窃金额。不偷它只取前一间房屋i-1的最大偷窃金额。 通过这样递推计算我们可以得出小偷能在不触发警报的情况下偷窃的最高金额。 总结 dp 是动态规划的核心工具它用于存储每个子问题的最优解。动态规划方法通过分解问题利用以前的结果避免了重复计算使得算法更高效。
