"Квадрат разлинован на N×N клеток (1 < N < 17). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вверх. По…
"Квадрат разлинован на N×N клеток (1 < N < 17). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вверх. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вверх— в соседнюю верхнюю. При попытке выхода за границу квадрата Робот разрушается. Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клетке маршрута Робота. Откройте файл. Определите максимальную и минимальную денежную сумму, которую может собрать Робот, пройдя из левой нижней клетки в правую верхнюю. В ответ запишите два числа друг за другом без разделительных знаков — сначала максимальную сумму, затем минимальную. 3.xlsx"
Класс, давай разберёмся по шагам и подсказками, чтобы ты смог разобраться и посчитать сам максимум и минимум.
Совет по задачке
- Исполнитель может двигаться только вправо или вверх, старт в левом нижнем углу, финиш в правом верхнем. Значит для любой клетки можно прийти либо слева, либо снизу.
- Нужно посчитать две величины: максимальную и минимальную сумму монет на пути, включая стартовую и конечную клетку. В ответе эти две цифры записываются подряд без разделителей (например, 1363 и 695 → 1363695).
Пошаговая подсказка (основа решения)
Введём две DP-таблицы того же размера N×N:
- max[i][j] — максимальная сумма, которую можно собрать, добравшись до клетки (i, j).
- min[i][j] — минимальная сумма до клетки (i, j). Здесь i обозначает «ряд» от нижнего края к верхнему, j — от левого края к правому.
Правила перехода (учти, что можно прийти только слева или снизу):
- Базовые: max[1][1] = min[1][1] = a[1][1], где a[i][j] — монета в клетке (i, j).
- Для первой вертикали (j = 1): max[i][1] = a[i][1] + max[i-1][1], min[i][1] = a[i][1] + min[i-1][1] при i > 1.
- Для первого ряда (i = 1): max[1][j] = a[1][j] + max[1][j-1], min[1][j] = a[1][j] + min[1][j-1] при j > 1.
- Общий случай (i > 1 и j > 1):
- max[i][j] = a[i][j] + max( max[i-1][j], max[i][j-1] )
- min[i][j] = a[i][j] + min( min[i-1][j], min[i][j-1] )
Итог:
- Максимальная сумма — max[N][N].
- Минимальная сумма — min[N][N].
- Ответ записывается как конкатенация: максимальная сумма сначала, затем минимальная (например, 1363 и 695 → 1363695).
Практическая реализация:
- Если делаешь на бумаге или в Excel:
- Размести исходные значения монет в сетке a[i][j].
- Построй две дополнительные сетки: одна для max, другая для min.
- Заполни по правилам перехода сверху вниз и слева направо.
- В конце в клетке (N, N) будут max и min — возьми их и соедини в нужном формате.
- Если делаешь на бумаге или в Excel:
Дополнительный чек
- Длина пути фиксирована: тебе понадобится ровно 2N − 1 клетка, чтобы перейти от стартовой до финишной точки, с N−1 шагами вверх и N−1 шагами вправо.
- Значения монет от 1 до 100, так что размах сумм остаётся в разумных пределах для N ≤ 16.
Если хочешь, могу проверить твой конкретный подход на примере или помочь с формулами в Excel шаг за шагом. Какой путь тебе удобнее использовать: чистый DP в голове/на бумаге, или в Excel? Поставь лайк или дизлайк, чтобы я знал, что подходит.
