В городе есть N улиц, и на каждой улице есть одна сокровищница с определенным количеством золотых монет - C (1) .... C (N) в нем.Поскольку грабитель умен, чтобы не быть пойманным, если он грабит в доме на данной улице, он не грабит в домах на двух улицах, граничащих с домом, обворованным (либо слева, либо справа).Таким образом он избегает понимания среди людей, и его риск уменьшен.Учитывая N и монеты C (i) (где i = 1 до N) в каждой сокровищнице, найдите максимальное количество золотых монет M, которое может получить грабитель.
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();
}
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];
}
}
для ввода:
7
10 20 15 1 9 12 5
выход:
32
, но в соответствии с вышеприведенной реализацией полученный вывод составляет 39
также для ввода:
10
5 6 6 16 30 15 13 16 19 27
выход:
63
, но в соответствии с вышеприведенной реализацией полученный результат составляет 84