"Квадрат разлинован на N×N клеток (1 < N < 17). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вверх. По…
"Квадрат разлинован на N×N клеток (1 < N < 17). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вверх. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вверх— в соседнюю верхнюю. При попытке выхода за границу квадрата Робот разрушается. Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клетке маршрута Робота. Откройте файл. Определите максимальную и минимальную денежную сумму, которую может собрать Робот, пройдя из левой нижней клетки в правую верхнюю. В ответ запишите два числа друг за другом без разделительных знаков — сначала максимальную сумму, затем минимальную. 3.xlsx"
Класс, давай разберёмся по шагам.
- Что нужно сделать
- Игрок move вправо или вверх, начиная с левого нижнего угла и заканчивая в правом верхнем.
- На каждой клетке лежит монета от 1 до 100. Нужно найти:
- максимальную сумму монет на таком пути,
- минимальную сумму монет на таком пути.
- Ответ должен быть записан как две цифры подряд: сначала max, потом min. Например 1363695 означает max = 1363, min = 695.
- Как посчитать корректно Используем динамическое программирование (DP). Пусть coin[i][j] — значение монеты в клетке с координатами (i, j), где i идёт слева направо (1..N), а j идёт снизу вверх (1..N). Тогда:
- Максимальная сумма до клетки (i, j):
maxDP[i][j] = coin[i][j] + max(maxDP[i-1][j], maxDP[i][j-1])
Базовые случаи:
- maxDP[1][1] = coin[1][1]
- для первого столбца maxDP[i][1] = coin[i][1] + maxDP[i-1][1]
- для первого ряда maxDP[1][j] = coin[1][j] + maxDP[1][j-1]
- Минимальная сумма до клетки (i, j): minDP[i][j] = coin[i][j] + min(minDP[i-1][j], minDP[i][j-1]) аналогично базовые случаи для min.
Итог:
- Максимальная сумма: maxDP[N][N]
- Минимальная сумма: minDP[N][N]
- Ответ в задаче: конкатенация этих двух чисел: сначала maxDP[N][N], затем minDP[N][N].
Что получается в твоём случае По данным решения и примерам, максимальная сумма равна 1363, минимальная — 695. Следовательно правильный ответ — 1363695.
Твой ответ На данный момент ты ничего не ответил: “Ученик не дал ответ на задание”. Это верный факт, но чтобы тренироваться, давай попробуем проверить ответ вместе. Хоть и не зная исходную сетку монет, итоговый результат по приведённому решению — 1363695.
Хочешь, могу привести пример на небольшой 3x3 сетке и пройти DP по шагам, чтобы наглядно увидеть, как формируются maxDP и minDP и как приходят числа 1363 и 695 (наглядно это помогут понять логику)? После объяснения можно ещё потренироваться на другой вариант задачи.
Пожалуйста, оцени мой ответ лайком или дизлайком.
