CODEWITHSUNDEEP
algorithmdynamic-programming
srip
srip

Reputation: 637

Leetcode House robber

I was trying House Robber problem(dp problem) on leet code. This solution from one of the user GYX looks simple and elegant.

   int rob(vector<int>& num) {
   int n = num.size();
        if (n==0) return 0;
        vector<int> result(n+1,0);
        result[1] = num[0];
        for (int i=2;i<=n;i++){
            result[i] = max(result[i-1],result[i-2]+num[i-1]);
        }
        return result[n];
   }

But I just could not get my head around the logic. Please help me with the logic and also how to approach problems like this?

Upvotes: 10

Views: 3551

Answers (3)

SeasonalShot
SeasonalShot

Reputation: 2589

Take a look at this simple recursive code. Visulizing a problem solved in DP is hard at first glance. You should always work your way up to that from a low performant recursive code first. Here is a different version of the code:

p = [0, 1, 2, 3, 1, 2, 3, 1, 2, 5, 8, 2]
def R(i):
    if i == 1 or i == 2:
        return i
    else:
        return max(p[i] + R(i - 2), R(i - 1))

print(R(11))

This is also easily memoizable if you want to bring the efficiency up.

Upvotes: 2

aerin
aerin

Reputation: 22694

Basically the answer is f(n) = max( f(n-1), f(n-2) + arr[n] ) and you are asking why.

Let's suppose this array arr = [9,1,7,9] and f(n) is the function.

When the array is only [9], your max f(0) will be arr[0].

When the array is [9,1], your max f(1) is max(arr[0], arr[1]).

When the array is [9,1,7], if you select 7, you can't select 1 therefore f(n-2) + arr[n]. However, if you don't select 7, you max f(2) will be same as f(1) which is f(n-1).

When the array is [9,1,7,9], you need to drop both 1 & 7 and choose 9, 9. f(n) = max( f(n-1), f(n-2)+arr[n] ) equation satisfies this case.

Upvotes: 6

brijs
brijs

Reputation: 545

Suppose I store the amount in kth house in house[k].

Suppose now I store the maximum amount of money possible to loot from the first k houses(and first k only) in max[k].

Now consider no houses, so max[0]=0

Now considering only first house, max[1]=amount in house 1

Now considering first 2 houses,

max[2]={either max[1](implies we chose to loot house 1) or (amount in house 2 + maximum amount that I had looted until the house located 2 places before my current house)}={max(max[1],house[2]+max[0])}

Similarly for first 3 houses, max[3]=max(max[2],house[3]+max[1])

Observing this trend, it can be formulated that max[k]=max(max[k-1],house[k]+max[k-2]). This value is calculated till in the end when there are no more houses, we get the maximum amount that can be looted from these first n houses.

DP problems strike the head only when you have had some practice and familiarity before, and this always helps.

Upvotes: 6

Related Questions