проблема грабителя дома, как это сделать таким образом

Question

Вы профессиональный грабитель, планирующий грабить дома по улице. В каждом доме спрятана определенная сумма денег, единственное препятствие, мешающее вам ограбить каждый из них, - это то, что к соседним домам подключена система безопасности, и она автоматически свяжется с полицией, если два соседних дома были взломаны в одну и ту же ночь.

Учитывая список неотрицательных целых чисел, представляющих сумму денег в каждом доме, определите максимальную сумму денег, которую вы можете ограбить сегодня вечером, не предупреждая полицию.

Пример 1:

• Входные данные: [1,2,3,1]
• Выходные данные: 4
• Объяснение: Разбойный дом 1 (деньги = 1), а затем грабящий дом 3 (деньги = 3). Общая сумма, которую вы можете ограбить = 1 + 3 = 4.

Пример 2:

• Ввод: [2,7,9,3,1]
• Вывод: 12
• Объяснение: Роб-хаус 1 (деньги = 2), Роб-дом 3 (деньги = 9) и Роб-дом 5 (деньги = 1). Общая сумма, которую вы можете ограбить = 2 + 9 + 1 = 12.

class Solution {
public int rob(int[] nums) {
    int sim=0;
    int sum=0;
    int i,j;

    for(i=0;i<nums.length;i++,i++){
        sim+=nums[i];
    }
    for(j=1;j<nums.length;j++,j++){
        sum+=nums[j];
    }
    int r= Math.max(sim,sum);
    return r;
}
}

Как сделать эту логику, если длина массива нечетна? можем ли мы сделать так, чтобы вывод был корректным для четной длины, хотя

Answer 1

Ваше решение пропустить один дом после ограбления предыдущего. Это не всегда дает максимальный результат. Рассмотрим этот случай: [100, 1, 1, 100]. Согласно вашему решению, sim == 101 и sum == 101, однако, правильное решение будет 200. (грабя 0-й и 3-й дом).

Я предлагаю два возможных решения: 1. с использованием рекурсии, 2. используя dp.

Используя рекурсию, вы можете выбрать либо ограбить дом и пропустить следующий, либо не грабить дом и переходить к следующему. Таким образом, у вас будет два рекурсивных случая, которые приведут к O (2 ^ n) сложности времени и O (n) сложности пространства.

public int rob(int[] nums) {
    return robHelper(nums, 0, 0);
}

private int robHelper(int[] nums, int ind, int money) {
    if (ind >= nums.length) return money;

    int rec1 = robHelper(nums, ind+1, money);
    int rec2 = robHelper(nums, ind+2, money+nums[ind]);
    return Math.max(rec1, rec2);
}

ИспользованиеДП оптимизировал бы временную и пространственную сложность сверху решения. Вы можете отслеживать два значения: currMax и prevMax . В то время как prevMax - это максимальные деньги без учета предыдущего дома, currMax - это максимальные деньги с учетом предыдущего дома. Поскольку prevMax гарантирует, что деньги из предыдущего дома не включены, вы можете добавить деньги из текущего дома в prevMax и сравнить их с currMax , чтобы найти общий максимальный доходдо этого момента. Вот мое решение, использующее dp, O (n) сложность времени и O (1) сложность пространства:

public int rob(int[] nums) {
    int currmax = 0;
    int prevmax = 0;

    for (int i = 0; i < nums.length; i++) {
        int iSum = prevmax + nums[i];
        prevmax = currmax;
        currmax = Math.max(currmax, iSum);
    }
    return currmax;
}

Answer 2

Как указывает siralexsir88 в комментариях, недостаточно только проверять решения для ограбления четных / нечетных домов, поскольку может случиться так, что лучшая стратегия состоит в том, чтобы пропустить более одного домав ряд.

Данный пример иллюстрирует этот факт: предположим, у вас есть [1, 3, 5, 2, 1, 7], здесь индексы 3 и 4 должны быть пропущены, чтобы выбрать последние 7.

Предлагаемое решение

Эта проблема является типичным примером динамического программирования и может быть решена путем рекурсивного построения решения.

Для каждого дома есть дваварианты: вы либо ограбить его, наш вы не. Давайте отследим лучшее решение для обоих случаев и для каждого дома: назовем R[i] максимальная прибыль до i-го дома , если мы ограбим i-й дом . Давайте определим NR[i] таким же образом, чтобы не грабил i-й шланг .

Например, предположим, что у нас есть [1, 3]. В этом случае:

• R[0] = 1
• NR[0] = 0
• R[1] = 3 Наилучшая прибыль при ограблении дома № 1 составляет 3
• NR[1] = 1 Наилучшая прибыль, не грабя дом № 1, равна 1

Давайте также назовем P[i] прибыль, которая дает нам ограбление i-го дома. Мы можем построить наше решение рекурсивно в терминах R и NR следующим образом:

1) R[i] = NR[i-1] + P[i]
2) NR[i] = max(NR[i-1], R[i-1])
3) R[0] = P[0]
4) NR[0] = 0

Давайте разберем его.

Рекурсивное отношение 1) говорит, что если мы ограбимВ этом доме мы не должны были грабить предыдущий дом и, следовательно, взять не грабить лучший результат за предыдущий дом.

Рекурсивное отношение 2) говорит, что если мы не грабимВ этом случае наша оценка является лучшей из тех, которые грабят, а не грабят предыдущий. Это имеет смысл, потому что мы ничего не добавляем к нашей общей прибыли, мы просто сохраняем лучшую прибыль на данный момент.

3) и 4) - это только начальные условия для первого дома, которые должны иметь смысл доэта точка.

Вот фрагмент псевдопифон, который вычисляет наилучшую прибыль:

P = [1, 3, 5, 2, 1, 7] # The houses
R = [0] * len(P)
NR = [0] * len(P)

R[0] = P[0]

# We skip index 0
for i in range(1, len(P)):
    R[i] = NR[i-1] + P[i]
    NR[i] = max(NR[i-1], R[i-1])

# The solution is the best between NR and R for the last house
print max(NR[-1], R[-1])

Решение подразумевает отслеживание двух массивов (R[i] и NR[i])во время обхода домов, а затем сравнить результаты в конце. Если вы просто хотите получить максимальную прибыль, вы можете сохранить результаты R и NR для предыдущего дома и отказаться от них по мере продвижения. Однако, если вы хотите точно знать, какая последовательность домов приводит к наилучшему результату, вам необходимо отслеживать весь массив, и, как только вы закончите, вернитесь назад и восстановите решение.

Answer 3

private static int rob(int[] money) {
    int max = 0;

    for (int i = 0; i < money.length; i++) {
        int skips = 2;

        while (skips < money.length) {
            int sum = 0;

            for (int j = 0; j < money.length; j += skips) {
                sum += money[j];
            }

            if (sum > max) {
                max = sum;
            }
            skips++;
        }
    }

    return max;
}