1 題目描述

2 解題思路

2.1 正向動態(tài)規(guī)劃

從前向后找，我們記f(n,tmp)表示[0,n-1]的點中最大的偷竊金額總和為tmp，我們現(xiàn)在要考慮偷不偷n號點（下面的方法會超時！），step_now表示當前點偷，step_not_now表示當前點不偷

class Solution:def rob(self, nums: List[int]) -> int:l=len(nums)def f(n,tmp):if(n==l-1):return(tmp+nums[n])elif(n==l-2):return(tmp+max(nums[n],nums[n+1]))else:step_now=f(n+2,nums[n]+tmp)step_not_now=f(n+1,tmp)return(max(step_now,step_not_now))return(f(0,0))

?上述代碼中，同一個f(n,tmp)被多次使用，比較耗時。我們可以用一個字典將已經(jīng)求得的f(n,tmp)記錄下來。

class Solution:def rob(self, nums: List[int]) -> int:l=len(nums)dit={}def f(n,tmp):if((n,tmp) in dit):return(dit[(n,tmp)])if(n==l-1):dit[(n,tmp)]=tmp+nums[n]return(tmp+nums[n])elif(n==l-2):dit[(n,tmp)]=tmp+max(nums[n],nums[n+1])return(tmp+max(nums[n],nums[n+1]))else:step_now=f(n+2,nums[n]+tmp)step_not_now=f(n+1,tmp)dit[(n,tmp)]=max(step_now,step_not_now)return(max(step_now,step_not_now))return(f(0,0))

但是，這種方法的時間復雜度和空間復雜度是很高的

2.2 反向動態(tài)規(guī)劃

從最后一個往前推

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

這種方法的時間復雜度就低了很多

?

?

總結

以上是生活随笔為你收集整理的文巾解题 198. 打家劫舍的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。