Mark As Completed Discussion

Solving Dynamic Programming problems--A more intuitive approach

Solving Dynamic Programming Problems  A More Intuitive Approach

Another popular dynamic programming question is the House Robber problem.

The idea here is that robbers want to rob houses along a street and their only constraint is that they can't rob 2 adjacent houses. So what we need to do is to calculate the maximum amount of money that they can rob up to any point. Eventually, if they can propagate the max amount of money to rob at the i'th house and the i eventually becomes the last house then we can know the max amount of money we can get.

A good way to start thinking about this is to consider how much money can they make if they rob 0 houses? Obviously, the answer would be 0. We can slowly start thinking about how much money can be robbed from 1 house, 2 houses, 3 houses and so on. Eventually, that will give us n houses.

So back to the first case. If we rob 0 houses then we will make $0.

JAVASCRIPT
OUTPUT
:001 > Cmd/Ctrl-Enter to run, Cmd/Ctrl-/ to comment