## 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 <= 100`
• `0 <= 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
}
``````
Copy The Code &

Input

cmd
nums = [1,2,3,1]

Output

cmd
4

### #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];
}
};
``````
Copy The Code &

Input

cmd
nums = [1,2,3,1]

Output

cmd
4

### #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];
}
}
``````
Copy The Code &

Input

cmd
nums = [2,7,9,3,1]

Output

cmd
12

### #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;
}
``````
Copy The Code &

Input

cmd
nums = [2,7,9,3,1]

Output

cmd
12

### #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])
``````
Copy The Code &

Input

cmd
nums = [1,2,3,1]

Output

cmd
4

### #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;
}
}
}
``````
Copy The Code &

Input

cmd
nums = [1,2,3,1]

Output

cmd
4