Question

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.

Answer 1

To solve this problem , we will use dynamic programming .

At each step we have 2 choices or decisions to make and we will take the best decision in order to maximize the money.

Choice-1)At every ith index or house we can  rob that house and add the money to the amount collected till previous to previous house i.e (i-2)th house

Choice -2)Skip the current house

Below is the simple python code to understand and verify the above logic.
Code:

def rob_non_adjacent_houses(money_list):
    """

    :param money_list:
    :return: maximum amount of money that can be robbed from non-adjacent houses
    """

    # If we are at the ith house then there are two options available to us, either we can
    # rob that house and add the money to the amount collected
    # till previous to previous house i.e (i-2)th house  or we skip the current house.
    dp = [money_list[0], money_list[1]]
    for i in range(2, len(money_list)):
        dp.append(max(dp[i - 1], dp[i - 2] + money_list[i]))
    return dp[len(money_list) - 1]


if __name__ == '__main__':
    """
    main method to test the above method
    """
    print(rob_non_adjacent_houses([30, 40, 50, 20, 10, 40]))