← Все вопросы
Задание 18 КЕГЭ: робот на таблице с накоплением — это динамика по сетке?
16
В 18-м дают прямоугольную таблицу с числами, робот идёт из верхнего левого угла в правый нижний, ходит только вправо и вниз, собирает (или тратит) числа. Нужен максимум или минимум суммы. Чувствую, что перебор всех путей не вариант. Как правильно?
3 ответа
30
✓ Принятый ответ — помог автору
Да, это динамическое программирование по сетке. В каждую клетку можно прийти только сверху или слева, поэтому лучший результат для клетки = её значение плюс лучший из двух соседей.
# grid — список списков чисел
rows, cols = len(grid), len(grid[0])
dp = [[0]*cols for _ in range(rows)]
dp[0][0] = grid[0][0]
for r in range(rows):
for c in range(cols):
if r == 0 and c == 0:
continue
best = float('-inf')
if r > 0:
best = max(best, dp[r-1][c]) # пришли сверху
if c > 0:
best = max(best, dp[r][c-1]) # пришли слева
dp[r][c] = grid[r][c] + best
print(dp[rows-1][cols-1])
Для минимума меняешь max на min и -inf на +inf. Реальное 18-е в КЕГЭ часто дают в виде файла-таблицы (Excel) и просят И максимум, И минимум — считаешь двумя проходами. Перебор всех путей экспоненциальный, а ДП линейное по числу клеток.
Снежана Фролова В 18-м почти всегда просят и макс, и мин одним заходом — два dp · 12 месяцев назад
Иван Сергеев Первая строка и первый столбец заполняются накопительно, это частая ловушка · 12 месяцев назад
10
Динамика по сетке: dp[r][c] = grid[r][c] + max(dp[r-1][c], dp[r][c-1]).
3
ДП на сетке.
Ваш ответ
Войдите, чтобы ответить на вопрос.