сумма прохождения лабиринта

Question

указана сетка NxN.каждой точке присваивается значение, скажем, num

, начиная с 1,1, мы должны перейти к N, N.

, если i, j - текущая позиция, мы можем идти вправо или вниз.Как найти минимальную сумму цифр путем обхода от 1,1 до n, n по любому пути, любые две точки могут иметь одинаковое число, например

1 2 3

4 5 6

7 8 9

1 + 2 + 3 + 6 + 9 = 21 n <= 10000000000 </p>

Выход 21 Может кто-нибудь объяснить, как подойти к проблеме?

Answer 1

Это проблема динамического программирования. Подзадача здесь - это минимальная стоимость / путь, чтобы добраться до любого данного квадрата. Поскольку вы можете двигаться только вниз и вправо, есть только два квадрата, которые могут позволить вам войти в данный квадрат, один сверху и один слева. Поэтому стоимость попадания в квадрат (i, i) составляет min(cost[i-1][i], cost[i][i-1]) + num. Если это выведет вас за пределы, рассмотрите только тот вариант, который находится внутри сетки. Рассчитайте каждый ряд слева направо, сначала сделайте верхний ряд и двигайтесь вниз. Стоимость, которую вы получите по (N, N), будет минимальной.

Answer 2

Вот мое решение с динамическим программированием в O(n^2)

вы начинаете с (1,1), так что вы можете найти, например, a = (1,2) и b = (2,1) по a = value (1,1) + value (1,2). Затем, чтобы найти (2,2), выберите минимум (a+ value(2,2)) and (b + value(2,2)) и продолжайте эту логику. Вы можете найти любую минимальную сумму среди (1,1) и (i, j) с этим алгоритмом. Позвольте мне объяснить,

Данная матрица

1 2 3

4 5 6

7 8 9

Кратчайший путь:

1 3 . 
5 . . 
. . . 

чтобы найти (2,2), возьмите исходное значение (2,2) = 5 из заданной матрицы и выберите m in(5 + 5), 3 + 5) = 8. так

Кратчайший путь:

1 3 6 
5 8 . 
12 . .

чтобы найти (3,2) выберите min (12 + 8, 8 + 8) = 16 and (2,3) = min(8 + 6, 6 + 6) = 12

Кратчайший путь:

1 3 6 
5 8 12 
12 16 . 

так что последний (3,3) = min (12 + 9, 16 + 9) = 21

Кратчайший путь:

из (1,1) в любую точку (i, j)

1 3 6 
5 8 12 
12 16 21

Answer 3

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

start--1--+--2--+--3--+
          |     |     |
          4     5     6
          |     |     |
          +--5--+--6--+
          |     |     |
          7     8     9
          |     |     |
          +--8--+--9--end

Answer 4

Если вы хотите стать действительно модным или работать с массивными матрицами, A * также может быть вариантом.

Answer 5

Попытка:

Начните с первой строки, рассчитайте кумулятивные значения и сохраните их.
Перейдите ко второй строке, теперь значения могли приходить только слева или сверху (поскольку вы можете идти только влево или вниз), рассчитайте наименьшее из совокупных значений для этой строки.
Перебирайте строки до последнего, и вы сможете получить наименьшее значение при достижении последнего узла.

Я утверждаю, что этот алгоритм - O (n), поскольку, если вы используете двумерный массив, вам нужно всего лишь дважды получить доступ ко всем полям (чтение сверху, слева) для чтения и один раз для записи.

Answer 6

Может кто-нибудь объяснить, как подойти к проблеме?

Читайте о динамическом программировании и переходите оттуда.