← Все вопросы

Задание 18 КЕГЭ: робот на таблице с накоплением — это динамика по сетке?

Задан 12 месяцев назад559 просмотров3 ответа
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

ДП на сетке.

Ваш ответ

Войдите, чтобы ответить на вопрос.
Поддержать проект