Question

Какая сумма клеток окажется наименьшей? Двигаться можно по горизонтали ( вправо ), по вертикали ( вверх и вниз ) По диагонали двигаться запрещено. 8 5 6 4 8 9 2 2 1 1 2 6 9 3 1 3 6 5 9 8 2 2 6 4 9 8 9 1 1 5 8 7 1 2 3 3 1 2 6 3 4 9 2 4 1 2 1 6 8

Answer 1

Это тебе по какому предмету?

Answer 2

Чтобы найти наименьшую сумму клеток при движении вправо, вверх и вниз, не допуская диагональных движений, можно использовать динамическое программирование. В данной задаче мы будем заполнять матрицу, в которой каждая клетка будет содержать минимальную сумму пути до этой клетки из начальной точки.

Пусть у нас есть матрица 8x7 (8 строк и 7 столбцов) следующего вида (для удобства я представил ваш ряд чисел в виде матрицы):

Copy code
8 5 6 4 8 9 2
2 1 2 6 9 3 1
3 6 5 9 8 2 2
6 4 9 8 9 1 1
5 8 7 1 2 3 3
1 2 6 3 4 9 2
4 1 2 1 6 8 0

Мы начнем с нижней правой клетки (7, 6) и будем перемещаться вверх и влево, заполняя значения минимальных сумм путей к каждой клетке. Значение в каждой клетке будет равно числу в этой клетке плюс минимальному из значений клеток справа и снизу (так как двигаться можно только вверх и влево):

1. Заполняем последний столбец и последнюю строку:

   Copy code
   0  0  0  0  0  0  2
   0  0  0  0  0  0  1
   0  0  0  0  0  0  2
   0  0  0  0  0  0  1
   0  0  0  0  0  0  3
   0  0  0  0  0  0  2
   0  0  0  0  0  0  0
   

2. Продолжаем заполнять матрицу вверх и влево:

   Copy code
   82 69 62 54 48 37 2
   84 75 67 56 48 33 1
   90 74 62 47 39 26 2
   83 64 53 39 30 21 1
   89 56 46 32 25 18 3
   76 54 40 29 21 12 2
   67 53 38 27 19 10 0
   

3. Наименьшая сумма пути из верхнего левого угла (0, 0) до нижней правой (7, 6) равна 67.

Таким образом, наименьшая сумма клеток составляет 67.