×

# PROBLEM

Contest

Author: D. Vishnu Vardhan reddy

Tester: D. Vishnu Vardhan reddy

Editorialist: D. Vishnu Vardhan reddy

SIMPLE

recursion

# 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.

2★dvvr
112
accept rate: 0%

 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,498
×1,164
×329
×6

question asked: 13 Sep '18, 21:20

question was seen: 175 times

last updated: 13 Sep '18, 21:20