LeetCode#198打家劫舍 Python
程序员文章站
2022-03-28 14:27:36
...
题目地址:https://leetcode-cn.com/problems/house-robber/
动态规划,即使这么简单我还是写不对
注意:只要不进两个连续的房屋就不会报警,但是可以跨好几个房屋,只要它们屋里的现金相加结果最大
dp[n]表示前n个房屋能偷到的最大现金,那dp[n + 1] 就等于 dp[n - 1] + 第n + 1这个房屋里的现金num,和dp[n]这两个数中的最大值,即:dp[n + 1] = max(dp[n], dp[n- 1] + num)
class Solution:
def rob(self, nums: List[int]) -> int:
pre = cur = 0
for num in nums:
cur, pre = max(pre + num, cur), cur
return cur
谢谢题解区Krahets清晰简洁的分析和题解
class Solution:
def rob(self, nums: List[int]) -> int:
if not nums: return 0
if len(nums) == 1: return nums[0]
dp = [0 for _ in range(len(nums))]
dp[0] = nums[0]
dp[1] = max(dp[0], nums[1])
for i in range(2, len(nums)):
dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])
return dp[-1]