Last Updated on 2022-12-14 by Clay
題目
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.
Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.
Example 1:
Input: nums = [1,2,3,1] Output: 4 Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3). Total amount you can rob = 1 + 3 = 4.
Example 2:
Input: nums = [2,7,9,3,1] Output: 12 Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1). Total amount you can rob = 2 + 9 + 1 = 12.
Constraints:
1 <= nums.length <= 1000 <= nums[i] <= 400
這是一個非常經典的題目，我們扮演一個竊賊，然後在一排的房子中評估要如何才能偷竊到最多的錢。要注意的是不能連著偷，會觸發警報系統。
解題思路
DP
我的做法是把當前可能搶最多錢的方式紀錄起來。
- 由於不能連著偷，所以第一棟房子跟第二棟房子是互斥的，都保持原樣。
- 第三棟房子沒得選， 一定只能跟第一棟房子連著搶才能最大化，所以直接加上
nums[0] - 從第四棟房子開始（假設位置在
i上），可以從i-2和i-3中選一個比較值錢的當作上一個搶的選點。這是前前棟房子和前前前棟房子。 - 記錄到最後，要從最後一棟房子和倒數第二棟房子選一個更高的回傳
DP 複雜度
由於沒有另外儲存空間，直接存在輸入的陣列中，
| Time Complexity | O(n) |
| Space Complexity | O(1) |
C++ 範例程式碼
class Solution {
public:
int rob(vector<int>& nums) {
// Base case
if (nums.size() >= 3) {
nums[2] += nums[0];
}
else if (nums.size() == 1) {
return nums[0];
}
// Find the best rob path
for (int i=3; i<nums.size(); ++i) {
nums[i] += max(nums[i-2], nums[i-3]);
}
return max(nums[nums.size()-2], nums.back());
}
};Python 範例程式碼
class Solution:
def rob(self, nums: List[int]) -> int:
# Base case
if len(nums) >= 3:
nums[2] += nums[0]
elif len(nums) == 1:
return nums[0]
# Find the besst rob path
for i in range(3, len(nums)):
nums[i] += max(nums[i-2], nums[i-3])
return max(nums[-2], nums[-1])