Dare2Solve
The problem is to determine the maximum amount of money you can rob from a series of houses, where you cannot rob two adjacent houses.
If you rob a house, you cannot rob the house immediately following it. This means that for each house, you have two choices: either rob it and add its value to the total from two houses before, or skip it and take the total from the house before. This forms the basis of a dynamic programming solution.
dp
where dp[i]
represents the maximum amount of money that can be robbed up to the i
th house.dp[0]
to nums[0]
.dp[1]
to the maximum of nums[0]
and nums[1]
.2
to n-1
, set dp[i]
to the maximum of dp[i-1]
(skipping the current house) and nums[i] + dp[i-2]
(robbing the current house).dp[n-1]
will be the maximum amount of money that can be robbed.O(n), since we are iterating through the houses once.
O(n), due to the dp
array that stores the maximum money that can be robbed up to each house.
class Solution {
public:
int rob(vector<int>& nums) {
int n = nums.size();
if (n == 1) {
return nums[0];
}
vector<int> dp(n, 0);
dp[0] = nums[0];
dp[1] = max(nums[0], nums[1]);
for (int i = 2; i < n; i++) {
dp[i] = max(dp[i - 1], nums[i] + dp[i - 2]);
}
return dp[n - 1];
}
};
class Solution:
def rob(self, nums: List[int]) -> int:
n = len(nums)
if n == 1:
return nums[0]
dp = [0] * n
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
for i in range(2, n):
dp[i] = max(dp[i - 1], nums[i] + dp[i - 2])
return dp[n - 1]
class Solution {
public int rob(int[] nums) {
int n = nums.length;
if (n == 1) {
return nums[0];
}
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], nums[i] + dp[i - 2]);
}
return dp[n - 1];
}
}
var rob = function (nums) {
const n = nums.length;
if (n === 1) {
return nums[0];
}
const dp = Array(n).fill(0);
dp[0] = nums[0];
dp[1] = Math.max(nums[0], nums[1]);
for (let i = 2; i < n; i++) {
dp[i] = Math.max(dp[i - 1], nums[i] + dp[i - 2]);
}
return dp[n - 1];
};