题目描述
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。
示例
示例 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 。
解答方法
方法一：动态规划
思路
假设一共有 nn 个房子，每个房子的金额分别是H0 ,H 1,…,H
n−1，子问题 f(k) 表示从前 k 个房子（即 H0,H1 ,…,H
k−1）中能偷到的最大金额。那么：
当 k=0 时，没有房子，所以 f(0) = 0。
当 k=1 时，只有一个房子，偷这个房子即可，所以 f(1) = H_0。
当k≥2 时，k 个房子中最后一个房子是Hk−1。如果不偷这个房子，那么问题就变成在前 k−1 个房子中偷到最大的金额，也就是子问题 f(k−1)。如果偷这个房子，那么前一个房子Hk−2显然不能偷，其他房子不受影响。那么问题就变成在前k−2 个房子中偷到的最大的金额。两种情况中，选择金额较大的一种结果。
f(k)=max{f(k−1),Hk−1+f(k−2)}
代码
class Solution:
def rob(self, nums: List[int]) -> int:
prev = 0
curr = 0
for num in nums:
prev, curr = curr, max(curr, prev+ num)
return curr
网友评论