In a village, people build houses in the same side of the road. A thief plans to loot the village. He wants maximum amount of money without having any risk of getting caught. By some means, the villagers know that their adjacent house is being looted or not and thus they become alert. So the thief cannot loot contiguous two houses. Given that the thief knows the amount of money stored in each house and the road is straight and there is no turning, which is the most efficient algorithmic strategy to solve this problem?
(A) Brute-force
(B) Dynamic Programming
(C) Backtracking
(D) Divide and Conquer
Answer: (B)
Explanation:
If we take a closer look, the problem boils down to: Given an array with some finite size where each element represents a positive number, find the maximum sum such that no two elements are adjacent. Dynamic Programming is the efficient technique to solve this. The algorithm can be given as follows: Maintain an auxiliary array loot. loot[0] = arr[0] loot[1] = arr[1] loot[i] = max(loot[i - 1], loot[i - 2] + arr[i]), 2 <= i < n loot[n - 1] gives the maximum amount of money the thief can take away.
Whether you’re preparing for your first job interview or aiming to upskill in this ever-evolving tech landscape, neveropen Courses are your key to success. We provide top-quality content at affordable prices, all geared towards accelerating your growth in a time-bound manner. Join the millions we’ve already empowered, and we’re here to do the same for you. Don’t miss out – check it out now!
