📋 Условие
Открываем файл к данной задачке. В начале найдём максимальную сумму, используя динамическое программирование.
🔍 Подробное решение
Задание 18 посвящено работе с электронными таблицами. В задании используется исполнитель Робот, который может перемещаться по клеткам, выполняя команды вправо или вниз.
Условие задачи:
Робот движется из левой нижней клетки в верхнюю правую клетку, собирая максимальную сумму. В каждой клетке записано число. Робот может двигаться только вверх или вправо.
Решение в Excel — динамическое программирование:
1. Открыть файл к задаче
2. Выделить область всех ячеек с числами, вырезать и вставить на столбец правее
3. В каждой ячейке области будет лежать максимальная сумма, которую может собрать Робот, дойдя до этой клетки
4. Формула: =МАКС(ячейка_слева; ячейка_снизу) + текущая_ячейка
5. Функция МАКС выбирает, откуда нужно идти, чтобы сумма была максимальна
6. Распространяем формулу на всю область
Для минимального значения используется функция МИН вместо МАКС.
Демо 2022: Максимум = 721, Минимум = 640
Демо 2024: Максимум = 2167, Минимум = 718
Условие задачи:
Робот движется из левой нижней клетки в верхнюю правую клетку, собирая максимальную сумму. В каждой клетке записано число. Робот может двигаться только вверх или вправо.
Решение в Excel — динамическое программирование:
1. Открыть файл к задаче
2. Выделить область всех ячеек с числами, вырезать и вставить на столбец правее
3. В каждой ячейке области будет лежать максимальная сумма, которую может собрать Робот, дойдя до этой клетки
4. Формула: =МАКС(ячейка_слева; ячейка_снизу) + текущая_ячейка
5. Функция МАКС выбирает, откуда нужно идти, чтобы сумма была максимальна
6. Распространяем формулу на всю область
Для минимального значения используется функция МИН вместо МАКС.
Демо 2022: Максимум = 721, Минимум = 640
Демо 2024: Максимум = 2167, Минимум = 718
📚 Теория
Динамическое программирование. Оптимальный путь в таблице.
📐 Формула
dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + grid[i][j]