Игра в грабителя

Средняя

07 November 2023

Описание задачи #

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

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

Входные данные: []int (сумма, которую грабитель может украсть в соответствующем доме)

Выходные данные: int (максимальная сумма грабежа)

Ограничения #

Количество домов (длина массива) - от 1 до 100
Сумма денег в каждом доме находится в диапазоне от 0 до 400

Примеры #

Входные данные: [1, 2, 3, 1]

Ответ: 4

Оптимальное решение — первый и третий дом.
Входные данные: [2, 7, 9, 3, 1]

Ответ: 12

Оптимальное решение — первый, третий и пятый дом. ]
Входные данные: [1]

Ответ: 1

Так как дом всего один — он и есть оптимальное решение.
Входные данные: [2, 1]

Ответ: 2

Оптимальное решение — первый дом.
Входные данные: [100, 9, 10, 9, 1, 100]

Ответ: 210

Оптимальное решение — первый, третий и шестой дом. Этот пример важен, потому что в процессе ограбления выгоднее всего после третьего дома пропустить не один, а сразу два дома (т.е. перейти с нечетных домов, на четные).

Брутфорс решение #

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

package main

type seq struct {
	index int
	sum   int
}

func robBruteforce(nums []int) int {
	sequences := genAllSequences(nums)
	max := 0

	for _, sequence := range sequences {
		if sequence[len(sequence)-1].sum > max {
			max = sequence[len(sequence)-1].sum
		}
	}

	return max
}

func genAllSequences(nums []int) [][]seq {
	switch len(nums) {
	case 0:
		return [][]seq{
			{
				{sum: 0},
			},
		}
	case 1:
		return [][]seq{
			{
				{sum: nums[0]},
			},
		}
	case 2:
		max := nums[0]
		if nums[1] > max {
			max = nums[1]
		}

		return [][]seq{
			{
				{sum: max},
			},
		}
	}

	res := [][]seq{
		{
			{
				index: 0,
				sum:   nums[0],
			},
		},
		{
			{
				index: 1,
				sum:   nums[1],
			},
		},
		{
			{
				index: 0,
				sum:   nums[0],
			},
			{
				index: 2,
				sum:   nums[2] + nums[0],
			},
		},
	}

	for i := 3; i < len(nums); i++ {
		temp := make([][]seq, 0, len(res))
		for _, sequence := range res {
			last := sequence[len(sequence)-1]

			if last.index == i-2 || last.index == i-3 {
				tmpSeq := make([]seq, 0, len(sequence))
				tmpSeq = append(sequence, seq{
					index: i,
					sum:   last.sum + nums[i],
				})
				temp = append(temp, tmpSeq)
			} else {
				temp = append(temp, sequence)
			}
		}

		res = temp
	}

	return res
}

type Seq = {
	index: number
	sum:   number
}

export function robBruteforce(nums: number[]): number {
	const sequences = genAllSequences(nums)
	let max = 0

	debugger;

	sequences.forEach((sequence) => {
		const lastIndex = sequence.length - 1
		if (sequence[lastIndex].sum > max) {
			max = sequence[lastIndex].sum
		}
	})

	return max
}

function genAllSequences(nums: number[]): Seq[][] {
	switch (nums.length) {
	case 0:
		return [[
			{
				index: 0,
				sum: 0,
			},
		]];
	case 1:
		return [[
			{
				index: 0,
				sum: nums[0],
			},
		]];
	case 2:
		return [[
			{
				index: 0,
				sum: Math.max(nums[0], nums[1]),
			},
		]];
	}

	let res: Seq[][] = [
		[
			{
				index: 0,
				sum:   nums[0],
			},
		],
		[
			{
				index: 1,
				sum:   nums[1],
			},
		],
		[
			{
				index: 0,
				sum:   nums[0],
			},
			{
				index: 2,
				sum:   nums[2] + nums[0],
			},
		],
	]

	for (let i = 3; i < nums.length; i++) {
		let temp: Seq[][] = []

		res.forEach((sequence) => {
			const last = sequence[sequence.length - 1]

			if (last.index === i - 2 || last.index === i - 3) {
				const tmpSeq = [
					...sequence,
					{
						index: i,
						sum:   last.sum + nums[i],
					}
				]

				temp.push(tmpSeq)
			} else {
				temp.push(sequence)
			}
		})

		res = temp
	}

	return res
}

Оценка сложности #

По времени

Длина любой последовательности не может превышать n/2. После каждого дома возможно разветвление маршрута на 2 — пойти либо в дом через один, либо через два. Таким образом, общее количество маршрутов можно оценить как 2^n/2.

Так как для нахождения максимума нам нужно пройтись по каждому из этих маршрутов, итоговую оценку сложности можно также оценить в O(2^n/2).

По памяти

O((n/2) * 2^n/2) — дополнительная память для того, чтобы сохранить все возможные маршруты.

Оптимальное решение #

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

Предположим, что грабитель завершает ограбление на последнем доме, тогда как узнать максимальную сумму награбленного?

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

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

Алгоритм следующий:

Первые 2 элемента остаются неизменными (так как мы начинаем с этих домов)
Третий элемент массива заменяем на сумму первого элемента и оригинальное значение третьего элемента (так как в третий дом мы можем попасть только из первого)
Для всех последующих элементов массива заменяем i'ый элемент на сумму оригинального значения i'го элемента с максимальным из двух (i - 2 или i - 3)
Возвращаем максимальный элемент из последнего и предпоследнего.

package main

func rob(nums []int) int {
	switch len(nums) {
	case 0:
		return 0
	case 1:
		return nums[0]
	case 2:
		max := nums[0]
		if nums[1] > max {
			max = nums[1]
		}

		return max
	}

	nums[2] = nums[2] + nums[0]

	for i := 3; i < len(nums); i++ {
		max := nums[i-2]
		if nums[i-3] > max {
			max = nums[i-3]
		}

		nums[i] = max + nums[i]
	}

	max := nums[len(nums)-1]
	if nums[len(nums)-2] > max {
		max = nums[len(nums)-2]
	}

	return max
}

export function rob(nums: number[]): number {
    switch (nums.length) {
        case 0:
            return 0
        case 1:
            return nums[0]
        case 2:
            return Math.max(nums[0], nums[1])
    }

    nums[2] = nums[2] + nums[0]

    for (let i = 3; i < nums.length; i++) {
        const max = Math.max(nums[i - 2], nums[i - 3])
        nums[i] = max + nums[i]
    }

    return Math.max(nums[nums.length - 1], nums[nums.length - 2])
}

Оценка сложности #

По времени

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

По памяти

O(1) — дополнительная память константна, так как все изменения мы делали in-place.

Оригинал задачи на Leetcode

Algorithmics

Игра в грабителя

Описание задачи #

Ограничения #

Примеры #

Брутфорс решение #

Оценка сложности #

Оптимальное решение #

Оценка сложности #