House Thief Problem
Let's solve the House Thief problem using Dynamic Programming.
Statement
You are a professional robber, and after weeks of planning, you plan to rob some houses along a street. Each of these houses has a lot of money and valuables. Let’s say that you cannot rob houses adjacent to each other since they have security and burglar alarms installed.
Following the above-mentioned constraint and given an integer array, money, that represents the amount of money in each house, return the maximum amount of money you can steal tonight without alerting the police.
Let’s say you have an array of money as follows:
money: [1, 2, 3, 4, 5]
Considering we cannot rob the adjacent houses, we have six possible combinations that can possibly yield a substantial amount. Out of these combinations, we'll find one that yields the maximum money. The possible combinations are as under:
...