198. House Robber
你是一名專業的小偷，計劃沿著街道搶劫房屋。每個房子裡都有一定數量的錢，你不能搶劫每一間房子的唯一限制是相鄰的房子都有連接的安全系統，如果同一晚有兩間相鄰的房子被闖入，系統將自動聯絡警察。
給定一個整數數組 nums 代表每間房子的錢數，返回今晚你在不驚動警察的情況下能搶劫的最大金額。
範例：
輸入：nums = [1,2,3,1]
輸出：4
解釋：搶劫第1間房子（錢數 = 1），然後搶劫第3間房子（錢數 = 3）。你可以搶劫的總金額 = 1 + 3 = 4。
Python
from typing import List
class Solution:
def rob(self, nums: List[int]) -> int:
if not nums:
return 0
if len(nums) == 1:
return nums[0]
if len(nums) == 2:
return max(nums[0], nums[1])
dp = [0] * len(nums)
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
for i in range(2, len(nums)):
dp[i] = max(dp[i-1], nums[i] + dp[i-2])
return dp[-1]
16.57MB, 41ms
C++
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
int rob(vector<int>& nums) {
if (nums.empty()) {
return 0;
}
if (nums.size() == 1) {
return nums[0];
}
if (nums.size() == 2) {
return max(nums[0], nums[1]);
}
vector<int> dp(nums.size());
dp[0] = nums[0];
dp[1] = max(nums[0], nums[1]);
for (size_t i = 2; i < nums.size(); ++i) {
dp[i] = max(dp[i-1], nums[i] + dp[i-2]);
}
return dp.back();
}
};
9.44MB, 2ms
Javascript
/**
* @param {number[]} nums
* @return {number}
*/
var rob = function(nums) {
if (nums.length === 0) {
return 0;
}
if (nums.length === 1) {
return nums[0];
}
if (nums.length === 2) {
return Math.max(nums[0], nums[1]);
}
// Initialize the dp array
let dp = new Array(nums.length);
dp[0] = nums[0];
dp[1] = Math.max(nums[0], nums[1]);
// Fill the dp array
for (let i = 2; i < nums.length; i++) {
dp[i] = Math.max(dp[i - 1], nums[i] + dp[i - 2]);
}
// Return the result
return dp[dp.length - 1];
};
48.77MB, 47ms
