題意：一組直線排列的房屋，一個小偷要進屋偷錢，如果小偷偷了相鄰兩座房屋就會觸發報警系統，問在不觸發報警系統的前提下小偷最多可以偷到多少錢。

難度：esay

思路：這是一道標準的動態規劃問題，創建一個list保存小偷到每個房間能拿到最多的錢，第一個房間為本身，第二個為前兩個房間較大者。第i個房間便為（狀態轉移方程）：

dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]) class Solution(object):def rob(self, nums):""":type nums: List[int]:rtype: int"""dp = [0] * len(nums)if not nums:return 0elif len(nums) == 1:return nums[0]dp[0] = nums[0]dp[1] = max(nums[0], nums[1])for i in range(2, len(nums)):dp[i] = max(nums[i] + dp[i - 2], dp[i - 1])return dp[-1]

?

?

?

?

?

總結

以上是生活随笔為你收集整理的LeetCode 198 House Robber Python的全部內容，希望文章能夠幫你解決所遇到的問題。

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