House Robber

Problem: 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 system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

Example:

Input: nums = [3,6,11,7,1]
Output: 15
Explanation: Rob house 1 (amount = 3), rob house 3 (amount = 11) and rob house 5 (amount = 1).
             Total amount you can rob = 3 + 11 + 1 = 15.

Approach: We can see it is a DP problem. Let's have an array Table where Table[i] will tell the maximum amount of money can be robbed till ith house. We can fill the Table in following way:

1. Table[0] = nums[0] as only one house is there.
2. Table[1] = Max(nums[0], nums[1]). In case of 2 house we just collect the money from the house which has the maximum amount of money.
3. Table[i] = Max(Table[i - 1], Table[i - 2] + nums[i]). Here what we are doing is at every house we are deciding which amount is greater; maximum amount collected till before previous house(Table[i - 2]) + amount in current house(nums[i]) or maximum amount collected till previous house(Table[i - 1]).

Obviously Table[n - 1] will be our answer. Can we do any improvement? Yes, If we look closely we are just using (i - 1) and (i - 2) values to decide the current(i) amount of money so we can use just 2 variables to hold these values instead of having the whole table. In this way our space complexity will become O(1) instead of O(n).

Implementation in C#:

    public int Rob(int[] nums)

    {

        int length = nums?.Length ?? 0;

        if (length == 0)

        {

            return 0;

        }

        if (length == 1)

        {

            return nums[0];

        }

        if (length == 2)

        {

            return Math.Max(nums[0], nums[1]);

        }

        int prev1 = nums[0];

        int prev2 = Math.Max(nums[0], nums[1]);

        for (int i = 2; i < length; ++i)

        {

            int curr = Math.Max(prev1 + nums[i], prev2);

            prev1 = prev2;

            prev2 = curr;

        }

        return prev2;

    }

Complexity: O(n)