LeetCode Solutions
198. House Robber
Time: $O(n)$ Space: $O(n)$
class Solution {
public:
int rob(vector<int>& nums) {
if (nums.empty())
return 0;
if (nums.size() == 1)
return nums[0];
// dp[i] := max money of robbing nums[0..i]
vector<int> dp(nums.size());
dp[0] = nums[0];
dp[1] = max(nums[0], nums[1]);
for (int i = 2; i < nums.size(); ++i)
dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);
return dp.back();
}
};
class Solution {
public int rob(int[] nums) {
final int n = nums.length;
if (n == 0)
return 0;
if (n == 1)
return nums[0];
// dp[i] := max money of robbing nums[0..i]
int[] dp = new int[n];
dp[0] = nums[0];
dp[1] = Math.max(nums[0], nums[1]);
for (int i = 2; i < n; ++i)
dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
return dp[n - 1];
}
}
class Solution:
def rob(self, nums: List[int]) -> int:
if not nums:
return 0
if len(nums) == 1:
return nums[0]
# dp[i]: = max money of robbing nums[0..i]
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], dp[i - 2] + nums[i])
return dp[-1]