Explanation of the Recursive Formula

• By using Dynamic Programming, we can get the maximum amount of money step by step.

For every house along the street, there are two situations,

1. If the previous house had been robbed, we can't rob the current house,

``````currentMaxValue = max(previousNoRobbery, previousYesRobbery);
``````

2. If the previous house hadn't been robbed, we can rob the current house,

``````currentMaxValue = moneyOfCurrentHouse + previousNoRobbery
``````

Here's the code:

``````int rob(vector<int> &num) {
int preNoRob = 0, preYesRob = 0;

for(int i = 1; i <= num.size(); ++i) {
int preNoRobTemp = preNoRob;
preNoRob = max(preNoRob, preYesRob); // situation 1
preYesRob = num[i-1] + preNoRobTemp; // situation 2
}
return max(preNoRob, preYesRob);
}``````

• I was trying to use a real example to figure out this algo, but somehow I can't seem to get correct answer following the step. Could you show me where I did wrong in my logic?

``````num=[1,2,3,2,4], answer should be 7 (3+4)

step(i, or setup)_______0_______1_____2______3______4

temp_______________Null______0_____0______1______2

preNo________________0______0_____1_______2______4

preYes_______________0______1_____2_______4______6
``````

and will return 6 as answer......where did my logic go wrong?

• num=[1,2,3,2,4], answer should be 8 (1+3+4),

step(num)___________0_______1(1)_____2(2)______3(3)______4(2)______5(4)

temp_______________Null______0_______0________1________2_______4

preNo________________0______0_______1________2________4_______4

preYes_______________0______1_______2________4________4_______8

1. In step 4, money of the 4th house = num[4 - 1] = 2. So, when (i = 4), preYes should be: num[4 - 1] + preNo = 2 + 2 = 4;

2. The fifth house (step 5, these are 5 house in this case) was forgotten;

@xkbb3144 gave a clear explanation above, please refer that.

• thanks, it seems like I completely didn't realize the fifth step.

• This post is deleted!

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.