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 theith house. When the thief reaches the ithhouse, he has two choices: to steal or not. Therefore, f(i) can be defined with the following equation:
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;
}
Read full article from Coding Interview Questions: No. 44 - Dynamic Programming on Stolen Values