描述
假設你是一個專業(yè)的竊賊，準備沿著一條街打劫房屋。每個房子都存放著特定金額的錢。你面臨的唯一約束條件是：相鄰的房子裝著相互聯(lián)系的防盜系統(tǒng)，且 當相鄰的兩個房子同一天被打劫時，該系統(tǒng)會自動報警。

給定一個非負整數(shù)列表，表示每個房子中存放的錢， 算一算，如果今晚去打劫，在不觸動報警裝置的情況下, 你最多可以得到多少錢 。

您在真實的面試中是否遇到過這個題？
樣例
樣例 1:

輸入: [3, 8, 4]
輸出: 8
解釋: 僅僅打劫第二個房子.
樣例 2:

輸入: [5, 2, 1, 3]
輸出: 8
解釋: 搶第一個和最后一個房子

動態(tài)規(guī)劃求解
考慮前i項的結果dp[i]時，

dp[i]為到達第i個房間時，得到的最大收益，A為房間錢數(shù)組。

當i = 1， 返回dp[0] = A[0]

當i = 2， 返回dp[1] = max(A[0], A[1])

當i = 3， 分為偷3號房屋和不偷3號房屋，

偷的情況下， 2號房間就不能偷了，結果為A[2] + dp[0]

不偷的情況下，結果為dp[1]

所以返回dp[2] = max(dp[0] + A[2], dp[1])

以此類推，dp[i] = max(dp[i-2] + A[i], dp[i-1])

class Solution:"""@param A: An array of non-negative integers@return: The maximum amount of money you can rob tonight"""def houseRobber(self, A):# write your code hereif not A:return 0dp = [0 for _ in A]dp[0] = A[0]for i in range(1, len(A)):if i == 1:dp[i] = max(dp[0], A[i])else:dp[i] = max(dp[i - 2] + A[i], dp[i - 1])return dp[-1] c=Solution() d=c.rob([3,8,4,13]) print(d)

輸出21

總結

以上是生活随笔為你收集整理的LeetCode 392打劫房屋 python的全部內容，希望文章能夠幫你解決所遇到的問題。

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