198. 打家劫舍
198.打家劫舍
定義dp[k]為偷到第k間屋子能獲得的最大金額和屎。
image.png
class Solution:
def rob(self, nums: List[int]) -> int:
n = len(nums)
if n == 0: return 0
elif n <= 2: return max(nums)
dp = [0] * n
dp[0] = nums[0]
dp[1] = max(nums[1], nums[0])
for i in range(1, n):
dp[i] = max(dp[i-2] + nums[i], dp[i-1])
return dp[n-1]
空間優(yōu)化：當(dāng)前狀態(tài)只與前兩個(gè)狀態(tài)有關(guān)：
def rob(self, nums):
n = len(nums)
if n == 0: return 0
elif n <= 2: return max(nums)
pre, cur = nums[0], max(nums[0], nums[1])
for i in range(2, n):
res = max(pre + nums[i], cur)
pre, cur = cur, res
return res
213. 打家劫舍 II
213.打家劫舍 II
解題思路：把環(huán)拆成兩個(gè)隊(duì)列枷邪，一個(gè)是從0到n-1，另一個(gè)是從1到n溅话，然后返回兩個(gè)結(jié)果最大的缎讼。
1.不偷最后一間
2.不偷第一間
結(jié)果取1澎语、2最大值熊户。
class Solution:
def rob(self, nums: List[int]) -> int:
n = len(nums)
if n == 0: return 0
elif n <= 3: return max(nums)
return max(self.eastRob(nums[1:]), self.eastRob(nums[:n-1]))
def eastRob(self, nums):
n = len(nums)
if n == 0: return 0
elif n <= 2: return max(nums)
pre, cur = nums[0], max(nums[0], nums[1])
for i in range(2, n):
res = max(pre + nums[i], cur)
pre, cur = cur, res
return res
