Почему это работает
- Посмотрим на последний дом из первых i: либо его не трогают, и лучшее — как для первых i − 1, либо его грабят, и тогда соседа нет, значит, лучшее для первых i − 2 плюс его деньги. Других вариантов нет.
- Грабить дом выгодно не всегда: дом 4 даёт 4, но тогда нельзя взять 7 рядом с ним, и 6 + 1 + 4 = 11 проигрывает 6 + 7 = 13 без него.
- Перебор пробует все наборы домов, их около 2ⁿ. Таблица хранит одно лучшее значение на префикс, и каждое строится из двух прежних клеток.
Сложность
Время O(n): по клетке на дом, каждая из двух прежних. Память O(n) на таблицу; читаются только две последние клетки, так что двумя переменными можно довести до O(1).
дальшеТеперь реши её сам, без подсказок.
Решить на LeetCode ↗