PROBLEM
Author: D. Vishnu Vardhan reddy
Tester: D. Vishnu Vardhan reddy
Editorialist: D. Vishnu Vardhan reddy
DIFFICULTY:
SIMPLE
PREREQUISITES:
PROBLEM:
There are ‘n’ cities in a line. Each city contains some value in it. A thief is going to steal the maximal value from these cities, but he can’t steal in two adjacent cities because police of the stolen city will alert his two neighboring cities, left and right side. What is the maximum stolen value ?
EXPLANATION:
While reaching city i thief has two options, either he robs it or leave it. Let dp[i] represents the maximum value stolen so far on reaching city i. We can calculate the value of dp[i] as following –
dp[i] = max (hval[i] + dp[i-2], dp[i-1])
hval[i] + dp[i-2] is the case when thief decided to rob city i. In that situation maximum value will be the current value of city + maximum value stolen till last robbery at city not adjacent to city i which will be city i-2.
dp[i-1] is the case when thief decided not to rob city i. So he will check adjacent city for maximum value stolen till now.
Thief will consider both options and decide whether to rob or not and maximum of both values will be the maximum stolen value till reaching city i.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.