Разбор

Перенумеруем дома начиная с первого индекса ($i$-ый дом содержит $a_i$ денег). Пусть $f(i)$ — максимальная сумма добычи после грабежа домов с $1$ по $i$-ый.

Тогда $f(1)=a_1,f(2)=max(a_1,a_2)$.

При вычислении $f(i)$ рассмотрим два случая:

• если $i$-ый дом грабится, то $(i-1)$-ый дом трогать нельзя. В таком случае прибыль составит $f(i-2)+a_i$.

  

• если $i$-ый дом не грабится, то прибыль составит $f(i-1)$.

  

Таким образом

Запомним значения $f(i)$ в массиве $res$. Ответом задачи будет значение $f(n)=res[n]$.

Пример

Рассмотрим вычисление $f(3)$. Если третий дом мы не грабим, то прибыль составит $f(2)=6$. Если третий дом грабится, то можно ограбить первый дом, получив прибыль $f(1)=6$ плюс прибыль за ограбление третьего дома, равную $2$ (общая прибыль составит $6+2=8$).

Рассмотрим вычисление $f(4)$. Если четвертый дом мы не грабим, то прибыль составит $f(3)=8$. Если четвертый дом грабится, то можно ограбить первые два дома, получив прибыль $f(2)=6$ плюс прибыль за ограбление четвертого дома, равную $10$ (общая прибыль составит $6+10=16$).

Упражнение

Вычислите значения $f(i)$ для следующих входных данных:

Реализация алгоритма

Объявим входной массив $a$ и результирующий $res$.

#define MAX 1000001
long long a[MAX], res[MAX];

Читаем входные данные.

scanf("%d",&n);
for(i = 1; i <= n; i++)
  scanf("%lld",&a[i]);

Вычисляем ответ для одного $re{s}_1$ и двух $re{s}_2$ домов.

res[1] = a[1];
if (n > 1) res[2] = max(a[1],a[2]);

Вычисляем ответы для остальных домов.

for(i = 3; i <= n; i++)
  res[i] = max(res[i - 2] + a[i], res[i - 1]);

Выводим ответ.

printf("%lld\n",res[n]);

Java реализация

import java.util.*; 

class Main 
{
  static long a[] = new long[1000001];
  static long res[] = new long[1000001];

  public static void main(String[] args) 
  {
    Scanner con = new Scanner(System.in);
    int n = con.nextInt();
    for(int i = 1; i <= n; i++)
      a[i] = con.nextInt();
    
    res[1] = a[1];
    if (n > 1) res[2] = Math.max(a[1],a[2]);

    for(int i = 3; i <= n; i++)
      res[i] = Math.max(res[i - 2] + a[i], res[i - 1]);

    System.out.println(res[n]);
    con.close();
  }
}

Python реализация

Читаем входные данные.

n = int(input())
lst = list(map(int,input().split()))

Инициализируем список $dp$.

dp = [0] * len(lst)

Вычисляем ответ для одного $d{p}_0$ и двух $d{p}_1$ домов.

dp[0] = lst[0]
if (n > 1): dp[1] = max(lst[0], lst[1])

Вычисляем ответы для остальных домов.

for i in range(2, len(lst)):
  dp[i] = max(dp[i-1], dp[i-2] + lst[i])

Выводим ответ.

print(dp[-1])