打家劫舍

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

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

示例 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 。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/house-robber

解决动态规划问题,需要列出其的dp方程,对于该题来说,我们可以设f(k) = 从前k个房间中能抢到的最大数 Ai = 第i个房间的钱数.
  k = 1时,f(1) = A1

k = 2 ,   f(2) = max(A1, A2)
k = 3 ,有两个选项 :1、抢第3个房子,将数额和第一个房子相加。  2、保持下现有最大数(抢第二个房子)
所以dp方程为 f(k) = max(f(k-1),  f(k-2) + n(k))    其中  f(k - 1)就是保持现有的最大值。
代码如下

class Solution:
    def rob(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 0:
            return 0
        if n == 1:
            return nums[0]
        x = nums[0]
        y = nums[1]
        z = [x]
        z.append(max(x, y))
        for i in range(2, n):
            z.append(max(z[i - 2] + nums[i], z[i - 1]))
        return z[-1]
点赞

发表评论

Title - Artist
0:00