【LeetCode 198】打家劫舍

本文主要是介绍【LeetCode 198】打家劫舍，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1. 题目

2. 分析

窃贼当天晚上的偷窃行为视昨晚有无偷窃而需要分类讨论：

• 如果前一天晚上有偷窃，那么今晚必定不能偷盗，所以最大的盗取值是dp[i-1]
• 如果前一天晚上没有偷窃，那么今晚可以偷窃，所以最大的盗取值是dp[i-2] + nums[i]
  然后递推比较这两个值谁大谁小即可。5min的题，不能再多了。

3. 代码

class Solution:def rob(self, nums: List[int]) -> int:dp = [0] * len(nums)dp[0] = nums[0]if len(nums) == 1:return dp[-1]dp[1] = max(nums[1], nums[0])for i in range(2, len(nums)):dp[i] = max(dp[i-1], dp[i-2] + nums[i])print(dp)return dp[-1]        

这篇关于【LeetCode 198】打家劫舍的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---