Explanation of the Recursive Formula


  • 17
    N

    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);
    }

  • 0
    C

    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?


  • 0
    X

    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


  • 0
    N
    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.


  • 0
    C

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


  • 0
    W
    This post is deleted!

Log in to reply
 

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