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.
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.
ReplyDeleteMuch clearer.
DeleteIt 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.
ReplyDeleteMy approach with DP
ReplyDeletepublic 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<>();
close.addAll(traverseCasas(houses, idx + 2, cache));
List far = new ArrayList<>();
far.addAll(traverseCasas(houses, idx + 3, cache));
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) {
cache.get(idx).add(idx);
}
return cache.get(idx);
}
What a wonderful post. I would like to say that this post is really very informational post. I really like it. programming assignments help
ReplyDeleteSzia,
ReplyDeleteHot! 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,
Radhey
Hey Brother,
ReplyDeleteHot! 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,
Radhey
Hi There,
ReplyDeleteIn total awe…. So much respect and gratitude to you folks for pulling off such amazing blogs without missing any points on the No. 44 - Dynamic Programming on Stolen Values. Kudos!
I joined the Amazon affiliate site and received my access key id and my secret key. There was a problem downlaoding and saving the secret key so I created another one. AWS Training USA ,I am submitting this information to Amazon to complete my affilaite site but Amazon is accepting the information.
I would appreciate any information as to why this may be ocurring.
I look forward to see your next updates.
Kind Regards,
Preethi.
Java jobs are becoming more plentiful as the use of this software is more and more common online. Those skilled in java applications are in demand now by telecommuting companies. These jobs allow you to work from home with java software. See more programming assignment help
ReplyDelete