## Saturday, February 23, 2013

### No. 44 - Dynamic Programming on Stolen Values

Problem: There are n houses built in a line, each of which contains some value in it. A thief is going to steal the maximal value in these houses, but he cannot steal in two adjacent houses because the owner of a stolen house will tell his two neighbors on the left and right side. What is the maximal stolen value?

For example, if there are four houses with values {6, 1, 2, 7}, the maximal stolen value is 13 when the first and fourth houses are stolen.

Analysis: A function f(i) is defined to denote the maximal stolen value from the first house to the ith house, and the value contained in the ith house is denoted as vi. When the thief reaches the ith house, he has two choices: to steal or not. Therefore, f(i) can be defined with the following equation:
It would be much more efficient to calculate in bottom-up order than to calculate recursively. It looks like a 1D array with size n is needed, but actually it is only necessary to cache two values for f(i-1) and f(i-2) to calculate f(i).

This algorithm can be implemented with the following C++ code:

int maxStolenValue(const vector<int>& values)
{
int length = values.size();
if(length == 0)
return 0;

int value1 = values[0];
if(length == 1)
return value1;

int value2 = max<int>(values[0], values[1]);
if(length == 2)
return value2;

int value;
for(int i = 2; i < length; ++i)
{
value = max<int>(value2, value1 + values[i]);
value1 = value2;
value2 = value;
}

return value;
}

More coding interview questions are discussed in my book <Coding Interviews: Questions, Analysis & Solutions>. You may find the details of this book on Amazon.com, or Apress.

The author Harry He owns all the rights of this post. If you are going to use part of or the whole of this ariticle in your blog or webpages, please add a reference to http://codercareer.blogspot.com/. If you are going to use it in your books, please contact him via zhedahht@gmail.com . Thanks.

1. It took me a while to understand this. I think a really easy way to explain this, is that if a field's value is greater than both of its neighbors (the combined values of whom you'd lose if you chose), then you choose that field. Thanks for posting this.

2. It took me a while to understand this. I think a really easy way to explain this, is that if a field's value is greater than both of its neighbors (the combined values of whom you'd lose if you chose), then you choose that field. Thanks for posting this.

3. Programming is very interesting and creative thing if you do it with love. Your blog code helps a lot to beginners to learn programming from basic to advance level. I really love this blog because I learn a lot from here and this process is still continuing.
Love from Pro Programmer

4. My approach with DP

public static int steal(int[] houses) {
Map> cache = new HashMap<>();
return traverseCasas(houses, -2, cache).stream().map(i -> houses[i]).reduce(0, (a, b) -> a + b);
}

private static List traverseCasas(int[] houses, int idx, Map> cache) {
if (cache.containsKey(idx) ) {
return cache.get(idx);
}

if (idx >= houses.length) {
return new ArrayList<>();
}

List close = new ArrayList<>();
List far = new ArrayList<>();

int sumClose = close.stream().map(i -> houses[i]).reduce(0, (a, b) -> a + b);
int sumfar = far.stream().map(i -> houses[i]).reduce(0, (a, b) -> a + b);

cache.put(idx, sumClose > sumfar ? close : far);
if (idx >= 0) {
}
return cache.get(idx);
}

5. What a wonderful post. I would like to say that this post is really very informational post. I really like it. programming assignments help

6. Szia,

Hot! That was HOT! Glued to the Dynamic Programming on Stolen Values your proficiency and style!

We have a customer in Denmark whose legal department is asking for the physical address of the data center in which their data is being processed. The region/AZ in question would be eu-west-1a+b.
Is there any chance AWS will disclose the address for this purpose?

I read multiple articles and watched many videos about how to use this tool - and was still confused! Your instructions were easy to understand and made the process simple.

Thanks,

7. Hey Brother,

Hot! That was HOT! Glued to the No. 44 - Dynamic Programming on Stolen Values your proficiency and style!

Unfortunately ,i revealed the access keys to my account by mistake on github yesterday evening which lead to unauthorized access AWS Training USA I got an email from AWS team notifying me the fraudulent activity yesterday and have followed the steps mentioned there. I have tried to terminate all unauthorized EC2 resources from my account.

But great job man, do keep posted with the new updates.

Regards,