Квадрат разлинован на $N \times N$ клеток ($1 < N < 26$). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот…
- 1
Начальную клетку включают в сумму бонусов. Для неё минимальная и максимальная суммы равны её бонусу.$$min[1][1] = max[1][1] = bonus[1][1]$$
- 2
Для каждой следующей клетки рассматривают только разрешённые переходы из клетки сверху и из клетки слева.$$min[i][j] = bonus[i][j] + \min(допустимые\ min[i-1][j],\ min[i][j-1])$$
Ещё 2 шага — в полном решении
Квадрат разлинован на $N \times N$ клеток ($1 < N < 30$). В каждой клетке лежит монета достоинством от 1 до 100. Робот начинает движение из левой верхней клетки и за одно перемещение может перейти…
- 1
Построим таблицу максимальных сумм. Для каждой клетки прибавляем её значение к большему из доступных результатов сверху и слева.$$M_{i,j}=a_{i,j}+\max(M_{i-1,j},M_{i,j-1})$$
- 2
Для демонстрационной таблицы максимальные суммы по строкам имеют вид: $1, 9, 17, 21$; $11, 10, 18, 24$; $12, 14, 30, 32$; $14, 17, 35, 41$.
Ещё 2 шага — в полном решении
Квадрат разлинован на $N \times N$ клеток ($1 < N < 30$). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде «вправо»…
- 1
Робот движется только вправо и вниз, поэтому в каждую клетку он может попасть только сверху или слева.$$M_{i,j}=a_{i,j}+\max(M_{i-1,j},M_{i,j-1})$$
- 2
Для минимальной суммы используется аналогичная рекуррентная формула с минимумом.$$m_{i,j}=a_{i,j}+\min(m_{i-1,j},m_{i,j-1})$$
Ещё 1 шаг — в полном решении
Квадратное поле имеет размер $N \times N$, где $1 < N < 30$. В каждой клетке находится монета достоинством от 1 до 100. Робот начинает движение из левой верхней клетки и может перемещаться только…
- 1
Считаем, что значение клетки входит в сумму маршрута, в том числе для начальной и конечной клеток.
- 2
Для каждой клетки заполняем две динамические таблицы: одну для максимальной, другую для минимальной суммы от начальной клетки до данной клетки. Переход разрешён только по отсутствующим стенам.
Ещё 2 шага — в полном решении
Квадрат разлинован на $N \times N$ клеток ($1 < N < 30$). В каждой клетке лежит монета достоинством от 1 до 100. Робот начинает движение из левой верхней клетки и может перемещаться только вправо…
- 1
Создаём две таблицы динамических значений: в одной храним максимальную сумму от начальной клетки до каждой достижимой клетки, в другой — минимальную сумму.$$M_{i,j}=a_{i,j}+\max(M_{i-1,j},M_{i,j-1}),\quad m_{i,j}=a_{i,j}+\min(m_{i-1,j},m_{i,j-1})$$
- 2
При вычислении клетки исключаем переходы, через которые проходит внутренняя стена. Недостижимым клеткам значения не присваиваем.
Ещё 1 шаг — в полном решении
Квадрат разлинован на $N \times N$ клеток ($1 < N < 26$). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот…
- 1
Обозначим через $m_{i,j}$ минимальную, а через $M_{i,j}$ максимальную сумму бонусов на пути из левой верхней клетки в клетку $(i,j)$.
- 2
Начальные значения для левой верхней клетки равны её бонусу: она входит в сумму маршрута.$$m_{1,1}=M_{1,1}=b_{1,1}$$
Ещё 3 шага — в полном решении
Квадрат разлинован на $N \times N$ клеток ($1 < N < 30$). Исполнитель Робот может перемещаться по клеткам только вправо или вниз. Между соседними клетками могут быть внутренние стены, через которые…
- 1
Создаём две таблицы динамического программирования: одну для максимальной суммы, другую для минимальной суммы монет при достижении каждой клетки.$$M_{i,j}=\text{максимальная сумма},\quad m_{i,j}=\text{минимальная сумма}$$
- 2
Для каждой клетки рассматриваем переход сверху и переход слева. Переход учитывается только в том случае, если между клетками нет стены.$$M_{i,j}=a_{i,j}+\max(\text{доступные значения }M),\quad m_{i,j}=a_{i,j}+\min(\text{доступные значения }m)$$
Ещё 2 шага — в полном решении
Квадрат разлинован на $N \times N$ клеток ($1 < N < 26$). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде «вправо»…
- 1
Робот делает только перемещения вправо и вниз, поэтому в каждую клетку он может попасть только из клетки сверху или из клетки слева.
- 2
Для каждой клетки строим две таблицы: максимальную и минимальную сумму монет на пути от начальной клетки до данной клетки.$$\mathrm{maxSum}_{i,j}=a_{i,j}+\max(\mathrm{maxSum}_{i-1,j},\mathrm{maxSum}_{i,j-1})$$
Ещё 2 шага — в полном решении
Квадрат разлинован на $N \times N$ клеток ($1 < N < 26$). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот…
- 1
Создаём две таблицы динамического программирования: в первой храним минимальную, во второй — максимальную сумму бонусов для каждого достижимого маршрута от левой верхней клетки до текущей.
- 2
Для каждой клетки рассматриваем переход из верхней клетки и из левой клетки. Переход исключается, если между клетками есть стена.
Ещё 2 шага — в полном решении
Квадрат разлинован на $N \times N$ клеток ($1 < N < 30$). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде «вправо»…
- 1
Робот движется только вправо и вниз, поэтому в клетку можно попасть только из клетки сверху или из клетки слева, если между клетками нет стены.
- 2
Для каждой клетки строятся два значения: максимальная и минимальная сумма монет на допустимом пути от начальной клетки до этой клетки.$$max[i][j] = a[i][j] + \max\limits_{(k,l)\to(i,j)} max[k][l]$$
Ещё 3 шага — в полном решении
Квадрат разлинован на $N \times N$ клеток ($1 < N < 26$). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде «вправо»…
- 1
Разобьём задачу на подзадачи: для каждой клетки вычислим минимальную и максимальную сумму платы на пути из левой верхней клетки в эту клетку.$$m_{i,j}=a_{i,j}+\min(m_{i-1,j},m_{i,j-1})$$
- 2
Аналогично вычислим максимальную сумму для каждой клетки.$$M_{i,j}=a_{i,j}+\max(M_{i-1,j},M_{i,j-1})$$
Ещё 2 шага — в полном решении
Квадрат разлинован на $N \times N$ клеток ($1 < N < 30$). В каждой клетке лежит монета достоинством от 1 до 100. Робот начинает движение из левой верхней клетки и может перемещаться только вправо…
- 1
Составим таблицу максимальных сумм. Для каждой клетки прибавляем её значение к большему из значений сверху и слева.$$M_{i,j}=a_{i,j}+\max(M_{i-1,j},M_{i,j-1})$$
- 2
Максимальная сумма в правой нижней клетке равна $41$.$$M_{4,4}=41$$
Ещё 2 шага — в полном решении
Квадрат разлинован на $N \times N$ клеток ($1 < N < 26$). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот…
- 1
Создайте для каждой клетки две величины: минимальную и максимальную сумму бонусов на пути из левой верхней клетки в эту клетку.
- 2
Для начальной клетки обе величины равны бонусу этой клетки.$$F_{1,1}^{\min}=F_{1,1}^{\max}=a_{1,1}$$
Ещё 3 шага — в полном решении
Квадрат разлинован на $N \times N$ клеток ($1 < N < 30$). В каждой клетке лежит монета достоинством от 1 до 100. Исполнитель Робот начинает движение из левой верхней клетки и может за одно…
- 1
Заполняем таблицу максимальных сумм. В каждой клетке берём максимум из достижимых соседних клеток сверху и слева и прибавляем стоимость монеты.$$M_{i,j}=a_{i,j}+\max(M_{i-1,j},M_{i,j-1})$$
- 2
Для примера максимальные суммы по строкам имеют вид: $1, 9, 17, 21$; $11, 20, 21, 24$; $12, 23, 33, 35$; $14, 26, 38, 44$.
Ещё 3 шага — в полном решении
Квадрат разлинован на $N \times N$ клеток ($1 < N < 26$). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде «вправо»…
- 1
Робот может попасть в каждую клетку только из клетки сверху или из клетки слева.$$S_{i,j}=a_{i,j}+S_{\text{предыдущая клетка}}$$
- 2
Для максимальной суммы в каждой клетке сохраняем большее из двух возможных накопленных результатов.$$\mathrm{max}_{i,j}=a_{i,j}+\max(\mathrm{max}_{i-1,j},\mathrm{max}_{i,j-1})$$
Ещё 2 шага — в полном решении
Квадрат разлинован на $N \times N$ клеток ($1 < N < 30$). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде «вправо»…
- 1
Считаем для каждой клетки две величины: максимальную и минимальную сумму монет на пути из левой верхней клетки в эту клетку. Начальная клетка получает значение, равное номиналу монеты в ней.$$M_{1,1}=m_{1,1},\quad L_{1,1}=m_{1,1}$$
- 2
Для каждой клетки рассматриваем только те клетки, из которых в неё можно перейти: верхнюю, если между клетками нет горизонтальной стены, и левую, если между клетками нет вертикальной стены.$$M_{i,j}=m_{i,j}+\max\limits_{(k,l)\to(i,j)} M_{k,l},\quad L_{i,j}=m_{i,j}+\min\limits_{(k,l)\to(i,j)} L_{k,l}$$
Ещё 2 шага — в полном решении
Квадрат разлинован на $N \times N$ клеток ($1 < N < 26$). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде «вправо»…
- 1
Робот может попасть в клетку только сверху или слева, поэтому для каждой клетки заполняются две таблицы: максимальных и минимальных сумм.$$M_{i,j}=a_{i,j}+\max(M_{i-1,j},M_{i,j-1})$$
- 2
Для минимальной суммы используется тот же переход с операцией минимума.$$m_{i,j}=a_{i,j}+\min(m_{i-1,j},m_{i,j-1})$$
Ещё 2 шага — в полном решении
Квадрат разлинован на $N \times N$ клеток ($1 < N < 30$). Исполнитель Робот может перемещаться по клеткам только вправо или вниз. Между соседними клетками могут быть внутренние стены, сквозь которые…
- 1
Построим таблицу максимальных сумм. Для каждой клетки складываем её значение с большим из значений, полученных из клетки сверху и клетки слева.$$M_{i,j}=a_{i,j}+\max(M_{i-1,j},M_{i,j-1})$$
- 2
Для правой нижней клетки максимальная сумма получается равной $41$.
Ещё 2 шага — в полном решении
Квадрат разлинован на $N \times N$ клеток ($1 < N < 30$). В каждой клетке лежит монета достоинством от 1 до 100. Робот начинает движение из левой верхней клетки и может перемещаться только вправо…
- 1
Составим для каждой клетки два значения: максимальную и минимальную сумму монет на пути из левой верхней клетки в эту клетку.
- 2
Для клетки $(i,j)$ рассмотрим все разрешённые переходы из клетки сверху и из клетки слева. Через стену переход не учитывается.
Ещё 3 шага — в полном решении
Квадрат разлинован на $N \times N$ клеток ($1 < N < 30$). Исполнитель Робот может перемещаться по клеткам только вправо или вниз. Между соседними клетками могут быть внутренние стены, через которые…
- 1
Сначала вычислим максимальные суммы для путей до каждой клетки. В первой строке и первом столбце путь однозначен.$$M_{1,1}=1$$
- 2
Для остальных клеток прибавляем значение монеты к большему из двух возможных предыдущих результатов.$$M_{i,j}=a_{i,j}+\max(M_{i-1,j},M_{i,j-1})$$
Ещё 3 шага — в полном решении