Algorithm
Problem Name: 198. House Robber
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
Code Examples
#1 Code Example with C Programming
Code -
C Programming
int robx(int *nums, int numsSize, int *t) {
int k1 = 0, k2 = 0;
if (numsSize == 1) return nums[0];
if (numsSize == 2) return nums[0] > nums[1] ? nums[0] : nums[1];
if (t[2] == -1) {
t[2] = robx(&nums[2], numsSize - 2, &t[2]);
}
k1 = nums[0] + t[2];
if (t[1] == -1) {
t[1] = robx(&nums[1], numsSize - 1, &t[1]);
}
k2 = t[1];
return k1 > k2 ? k1 : k2;
}
int rob(int* nums, int numsSize) {
#if 0
int k = 0;
int *t;
if (numsSize == 0) return 0;
t = malloc(numsSize * sizeof(int));
if (!t) return 0;
memset(t, -1, numsSize * sizeof(int));
k = robx(nums, numsSize, t);
free(t);
return k;
#else
int i;
int rob_p, dont_rob_p;
int rob_this, dont_rob_this;
rob_p = dont_rob_p = 0;
rob_this = dont_rob_this = 0;
for (i = 0; i < numsSize; i ++) {
rob_this = nums[i] + dont_rob_p;
dont_rob_this = (rob_p > dont_rob_p) ? rob_p : dont_rob_p;
rob_p = rob_this;
dont_rob_p = dont_rob_this;
}
return rob_this > dont_rob_this ? rob_this : dont_rob_this;
#endif
}
Input
Output
#2 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
int rob(vector<int>& nums) {
int n = nums.size();
if(n < 2) return n ? nums[0] : 0;
vector<int>dp(n);
dp[0] = nums[0], dp[1] = max(nums[0], nums[1]);
for(int i = 2; i < n; i++)
dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]>;
return dp[n - 1];
}
};
Input
Output
#3 Code Example with Java Programming
Code -
Java Programming
class Solution {
public int rob(int[] nums) {
if (nums.length == 1) {
return nums[0];
}
int[] dp = new int[nums.length];
dp[0] = nums[0];
dp[1] = Math.max(nums[0], nums[1]);
for (int i = 2; i < nums.length; i++) {
dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
}
return dp[nums.length - 1];
}
}
Input
Output
#4 Code Example with Javascript Programming
Code -
Javascript Programming
function rob(nums) {
if (nums.length == 0) return 0;
let prev1 = 0;
let prev2 = 0;
for (let num of nums) {
let tmp = prev1;
prev1 = Math.max(prev2 + num, prev1);
prev2 = tmp;
}
return prev1;
}
Input
Output
#5 Code Example with Python Programming
Code -
Python Programming
class Solution:
def rob(self, nums):
if len(nums) <= 2: return max(nums or [0])
nums[2] += nums[0]
for i in range(3, len(nums)): nums[i] += max(nums[i - 2], nums[i - 3])
return max(nums[-1], nums[-2])
Input
Output
#6 Code Example with C# Programming
Code -
C# Programming
using System;
namespace LeetCode
{
public class _0198_HouseRobber
{
public int Rob(int[] nums)
{
int p2Amount = 0, p1Amount = 0;
foreach (var money in nums)
{
var currentAmount = Math.Max(p2Amount + money, p1Amount);
p2Amount = p1Amount;
p1Amount = currentAmount;
}
return p1Amount;
}
}
}
Input
Output