Похоже, это разновидность проблемы LeetCode House Robber, но я нашел, что ее значительно сложнее решить:
Есть дома, расположенные на сетке NxN.Известно, что каждый дом содержит некоторое количество ценностей.Задача грабителей - ограбить как можно больше домов, чтобы максимизировать количество добычи.Однако система безопасности установлена, и если вы грабите два соседних дома (слева, справа, сверху и снизу), сработает сигнализация.Найдите максимальную добычу, которую грабитель может ограбить.
Houses : alignment
10 20 10 0 1 0
20 40 20 => 1 0 1
10 20 10 0 1 0
This alignment results in the maximum of 80.
Я узнал, как решить оптимальный выбор домов для одного ряда с динамическим программированием из https://shanzi.gitbooks.io/algorithm-notes/problem_solutions/house_robber.html:
public class HouseRobber {
public int rob(int[] nums) {
if (nums.length == 0) return 0;
if (nums.length == 1) return nums[0];
int[] dp = new int[nums.length];
dp[0] = nums[0];
int max = dp[0];
for (int i = 1; i < dp.length; i++) {
dp[i] = nums[i];
// Do not need to check k < i - 3.
for (int j = 2; i - j >= 0 && j <= 3; j++) {
dp[i] = Math.max(dp[i], dp[i - j] + nums[i]);
}
max = Math.max(dp[i], max);
}
return max;
}
}
Но как только я выберу оптимальный выбор для одной строки, он может не совпадать с оптимальным выбором для строк выше и ниже этой строки.Даже если я найду оптимальную комбинацию для двух строк, следующая строка может иметь больше ценностей, чем две строки вместе, и потребует другой корректировки, и так далее, и так далее.
Это сложно, потому что переменных намного большечтобы рассмотреть, чем дома в одном ряду, и может быть более одного оптимального выравнивания, которые дают грабителю максимальную добычу (например, пример выше.)
Я нашел то, что казалось плохо написанным решением вPython, но так как я понимаю только языки на основе C (Java, C #, C ++), я не смог многого из этого извлечь.Может ли кто-нибудь помочь мне с решением или хотя бы с некоторыми указателями?
Спасибо за ваше время!