考察点:线性 DP 的『选/不选』取舍,以及滚动数组空间优化。
思路:对第 i 间房只有『偷』或『不偷』两种选择,取两者最大值。
要点(状态定义):
dp[i] = 考虑前 i 间房(第 i 间可选)能偷到的最大金额。dp[i] = max(dp[i-1], dp[i-2] + nums[i])——不偷第 i 间则继承 dp[i-1];偷则加上 nums[i] 并接 dp[i-2]。dp[0]=nums[0], dp[1]=max(nums[0],nums[1])。要点(实现与优化):
def rob(nums):
prev2 = 0
prev1 = 0
for x in nums:
prev2, prev1 = prev1, max(prev1, prev2 + x)
return prev1
题目与答案就在本页;收藏、批注和错题重练在应用内