Начинать можно с любой ячейки в верхнем ряду. Передвигаясь от нее вниз по диагонали хоть вправо, хоть влево, суммируйте числа, содержащиеся ...
Условие:
Начинать можно с любой ячейки в верхнем ряду. Передвигаясь от нее вниз по диагонали хоть вправо, хоть влево, суммируйте числа, содержащиеся в «посещаемых» вами квадратиках, пока не дойдете до нижнего ряда решетки. Нельзя сворачивать вбок или вверх. Нельзя прокладывать путь через поля с цифрой 1 или соседствующими с ними по горизонтали (но можно ст
Решение:
Хорошо, давайте разберемся с задачей. Вам нужно найти путь через решетку, начиная с любой ячейки в верхнем ряду и двигаясь только вниз по диагонали, чтобы получить максимальную сумму чисел.
Для начала, давайте рассмотрим пример решетки:
1 2 3
4 5 6
7 8 9
Мы можем начать с любой ячейки в верхнем ряду, например, с ячейки 2. Затем мы можем двигаться только вниз по диагонали, поэтому следующей ячейкой будет 5. Затем мы можем перейти в ячейку 8 и, наконец, в ячейку 9. Таким образом, максимальная сумма чисел на этом пути будет 2 + 5 + 8 + 9 = 24.
Теперь давайте рассмотрим более общий случай. Пусть у нас есть решетка размером n x n, где каждая ячейка содержит число. Мы можем использовать динамическое программирование для решения этой задачи.
Создадим двумерный массив dp размером n...
