Рубрики

Алгоритмы | Разное | Вопрос 11

В деревне люди строят дома на одной стороне дороги. Вор планирует разграбить деревню. Он хочет получить максимальную сумму денег без риска быть пойманным. В некоторой степени жители деревни знают, что их соседний дом разграблен или нет, и поэтому они становятся бдительными. Таким образом, вор не может разграбить смежные два дома. Учитывая, что вор знает, сколько денег хранится в каждом доме, а дорога прямая, а поворотов нет, какая стратегия алгоритма наиболее эффективна для решения этой проблемы?
(А) Грубая сила
(B) Динамическое программирование
(C) Возвращение
(D) разделяй и властвуй

Ответ: (Б)
Объяснение:

If we take a closer look, the problem boils down to:
Given an array with some finite size where each element represents 
a positive number, find the maximum sum such that no two elements 
are adjacent.
Dynamic Programming is the efficient technique to solve this. 
The algorithm can be given as follows:
Maintain an auxiliary array loot.
loot[0] = arr[0]
loot[1] = arr[1]
loot[i] = max(loot[i - 1], loot[i - 2] + arr[i]),  2 <= i < n
loot[n - 1] gives the maximum amount of money the thief can take away.

Тест на этот вопрос

Рекомендуемые посты:

Алгоритмы | Разное | Вопрос 11

0.00 (0%) 0 votes