A robber enters a colony of houses numbered from 1 to
n. Every house has a number printed on
the top of it. That number is the amount of money inside that house. However,
there is one constraint. If the robber cannot robs from money from consecutive
houses. How can the robber maximize his robbery?
Solution:
If Robber robs from i-th house, he can't rob house no i-1
and house no i+1.
Dynamic
Programming logic:
dp[i] = Math.max(dp[i - 2] + amPerHouse[i], dp[i - 1]);
Implementation in Java:
import java.util.Scanner;
public class MaximiseRobbery {
public static void main(String[] args) {
Scanner scan = new
Scanner(System.in);
int houses = scan.nextInt();
int[] amPerHouse = new
int[houses];
for (int
i = 0; i < houses; i++) {
amPerHouse[i] = scan.nextInt();
}
int maximumRobbery = maximizeRobbery(amPerHouse, houses);
System.out.println(maximumRobbery);
scan.close();
}
/**
*
Method to maximise the robbery
* @param amPerHouse
*/
private static int maximizeRobbery(int[]
amPerHouse,int
houses) {
if
(houses == 1) {
return amPerHouse[0];
} else
if (houses == 2) {
return Math.max(amPerHouse[0], amPerHouse[1]);
}
int[]
dp = new
int[amPerHouse.length];
dp[0] = amPerHouse[0];
dp[1] = amPerHouse[1];
for
(int i = 2; i < houses; i++) {
dp[i] = Math.max(dp[i - 2] + amPerHouse[i], dp[i - 1]);
}
return dp[houses - 1];
}
}
Reference:
No comments:
Post a Comment