198. 打家劫舍

你是一個專業(yè)的小偷，計劃偷竊沿街的房屋。每間房內都藏有一定的現金，影響你偷竊的唯一制約因素就是相鄰的房屋裝有相互連通的防盜系統，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統會自動報警。

給定一個代表每個房屋存放金額的非負整數數組，計算你 不觸動警報裝置的情況下 ，一夜之內能夠偷竊到的最高金額。

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/house-robber
著作權歸領扣網絡所有。商業(yè)轉載請聯系官方授權，非商業(yè)轉載請注明出處。

代碼：

from leetcode_python.utils import *class Solution:def __init__(self):passdef rob(self, nums: List[int]) -> int:if len(nums)<=2: return max(nums)dp_0 = nums[0]dp_1 = nums[1]for i in range(2,len(nums)):dp_0,dp_1 = max(dp_0,dp_1),dp_0+nums[i]return max(dp_0,dp_1)def rob_改進前(self, nums: List[int]) -> int:if len(nums)<=2: return max(nums)dp = [[0,0,0]for _ in range(len(nums))] # 左邊偷了，左邊一個沒偷，左邊兩個沒偷dp[0] = [0,nums[0],nums[0]]dp[1] = [nums[0],nums[1],max(nums[0:2])]for i in range(2,len(nums)):dp[i] = [max(dp[i-1][1:3]),dp[i-1][0]+nums[i],dp[i-2][0]+nums[i]]# print(dp)return max(dp[-1])def test(data_test):s = Solution()return s.rob(*data_test) def rob_改進前(data_test):s = Solution()return s.rob_改進前(*data_test)def test_obj(data_test):result = [None]obj = Solution(*data_test[1][0])for fun, data in zip(data_test[0][1::], data_test[1][1::]):if data:res = obj.__getattribute__(fun)(*data)else:res = obj.__getattribute__(fun)()result.append(res)return resultif __name__ == '__main__':datas = [# [[9,1,6,9,8]],[[2,7,9,3,1]],[[1,2,3,1]],[randListInt(1,100,20)]]for data_test in datas:t0 = time.time()print('-' * 50)print('input:', data_test)print('output[test]:', test(data_test))print('output[true]:', rob_改進前(data_test))print(f'use time:{time.time() - t0}s')

備注：
GitHub：https://github.com/monijuan/leetcode_python

CSDN匯總：模擬卷Leetcode 題解匯總_卷子的博客-CSDN博客

可以加QQ群交流：1092754609

leetcode_python.utils詳見匯總頁說明
先刷的題，之后用腳本生成的blog，如果有錯請留言，我看到了會修改的！謝謝！

總結

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

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