Нахождение веса минимального маршрута

Question

Дано поле размером (N, N) клеток (двумерный массив). В каждой клетке написано число – вес клетки. Вес маршрута вычисляется как сумма весов посещенных клеток.

Начальное положение исполнителя — верхняя левая клетка, конечное — нижняя правая.

Если исполнитель может передвигаться только на одну клетку вправо или вниз, то нижеприведенный код верно отобразит ответ для каждой клетки массива:

A = [
    [5, 6, 8, 0],
    [3, 5, 0, 1],
    [4, 4, 1, 1],
    [9, 9, 8, 8]
]

for i in range(len(A)):
    for j in range(len(A)):
        if i > 0 and j > 0:
            A[i][j] += min(A[i-1][j], A[i][j-1])
        else:
            if i > 0:
                A[i][j] += A[i-1][j]
            else:
                if j > 0:
                    A[i][j] += A[i][j-1]

for i in A:
    print(i)

Как будет выглядеть алгоритм, где исполнитель может двигаться на любое количество клеток вправо или вниз?

Answer 1

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

A = [
    [5, 6, 8, 0],
    [3, 5, 0, 1],
    [4, 4, 1, 1],
    [9, 9, 8, 8]
]
dp = [
    [5, 10000, 10000, 10000],
    [10000, 10000, 10000, 10000],
    [10000, 10000, 10000, 10000],
    [10000, 10000, 10000, 10000],
]
for i in range(0,len(A)):
    for j in range(0,len(A)):
        if i-1>=0:
            dp[i][j]=min(dp[i-1][j]+A[i][j],dp[i][j])
        if j-1>=0:
            dp[i][j]=min(dp[i][j-1]+A[i][j],dp[i][j])
for i in dp:
    print(i)

Это был пофикшенный код, у вас выдавал ошибку как это заметили в комментах А это решение::

A = [
    [5, 6, 8, 0],
    [3, 5, 0, 1],
    [4, 4, 1, 1],
    [9, 9, 8, 8]
]
dp = [
    [5, 10000, 10000, 10000],
    [10000, 10000, 10000, 10000],
    [10000, 10000, 10000, 10000],
    [10000, 10000, 10000, 10000],
]
for i in range(0,len(A)):
    for j in range(0,len(A)):
        if i-1>=0:
            x = 10000
            for ll in range(0,i):
                x=min(x,dp[ll][j])
            dp[i][j]=min(x+A[i][j],dp[i][j])
        if j-1>=0:
            x = 10000
            for ll in range(0, j):
                x = min(x, dp[i][ll])
            dp[i][j]=min(x+A[i][j],dp[i][j])
for i in dp:
    print(i)

БЛОГ НА HUSL

Нахождение веса минимального маршрута

Ответы (1 шт):