Как решать задание 18 ЕГЭ по информатике (робот, динамическое программирование)?

Задание 18 — робот идёт по прямоугольной таблице из левого верхнего угла в правый нижний, может двигаться только вправо и вниз, собирая числа. Нужны максимальная и минимальная сумма на пути.

Метод — динамическое программирование. Заполняешь таблицу сумм dp, где dp[i][j] — лучшая сумма пути до клетки (i, j). В каждую клетку приходишь либо сверху, либо слева:

dp[i][j] = a[i][j] + max(dp[i-1][j], dp[i][j-1])

Код (файл с таблицей через табы/пробелы):

grid = [list(map(int, line.split())) for line in open('18.txt')]
R = len(grid)
C = len(grid[0])
dp = [[0]*C for _ in range(R)]

for i in range(R):
    for j in range(C):
        best = []
        if i > 0: best.append(dp[i-1][j])
        if j > 0: best.append(dp[i][j-1])
        dp[i][j] = grid[i][j] + (max(best) if best else 0)
print(dp[R-1][C-1])   # максимум; для минимума замени max на min

Частые ошибки:

• неправильно обработать первую строку/столбец (туда приходишь единственным путём);
• перепутать направление обхода;
• для минимума забыть поменять max на min (две отдельные задачи!).

Иногда вместо таблицы дают исполнителя с командами — но суть та же: ДП по клеткам. Метод универсален и быстр.