помогите, пожалуйста, найти и исправить ошибку в коде

Question

В каждой клетке прямоугольной таблицы N×M записано некоторое число. Изначально игрок находится в левой верхней клетке. За один ход ему разрешается перемещаться в соседнюю клетку либо вправо, либо вниз (влево и вверх перемещаться запрещено). При проходе через клетку с игрока берут столько килограммов еды, какое число записано в этой клетке (еду берут также за первую и последнюю клетки его пути).

Требуется найти минимальный вес еды в килограммах, отдав которую игрок может попасть в правый нижний угол

мой код

b = list(map(int, input().split()))
a = []
for _ in range(b[1]):
    a.append(list(map(int, input().split())))
n = a[0][0]
p = 0
print(*a, sep="\n")
for i in range(1, b[1]):
    if p == a[i].index(min(a[i])):
        n += a[i][a[i].index(min(a[i]))]
        p = a[i].index(min(a[i]))
    elif a[i-1].index(min(a[i-1])) < a[i].index(min(a[i])):
        p = a[i].index(min(a[i]))
        for i2 in range(1,b[1]):
            n += a[i-1][i2]
        n += a[i][p]
    elif a[i-1].index(min(a[i-1])) > a[i].index(min(a[i])):
        n += a[i][p]
print(n)

Answer 1

Заполняете первую строку и первый столбец кумулятивными суммами по соответствующему направлению.

Обходите оставшуюся часть по строкам. Для каждой ячейки выбираете, что меньше - верхняя клетка или левая, и записываете минимум из них + значение в ячейке.

Результат в правой нижней

Answer 2

Инициализируйте dp[0][0] значением, записанным в клетке (0, 0).
Заполните первую строку и первый столбец массива dp, используя только движения вправо и вниз соответственно.
Для каждой клетки dp[i][j], начиная с dp[1][1], вычислите dp[i][j] как минимум из dp[i-1][j] и dp[i][j-1], прибавив к этому значению вес еды в клетке (i, j).
В конце dp[N-1][M-1] будет содержать минимальный вес еды, который нужно отдать, чтобы добраться до правого нижнего угла.

def min_food(grid):
    N, M = len(grid), len(grid[0])
    dp = [[0]*M for _ in range(N)]
    dp[0][0] = grid[0][0]

    # Заполните первую строку
    for j in range(1, M):
        dp[0][j] = dp[0][j-1] + grid[0][j]

    # Заполните первый столбец
    for i in range(1, N):
        dp[i][0] = dp[i-1][0] + grid[i][0]

    for i in range(1, N):
        for j in range(1, M):
            dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]

    return dp[-1][-1]

Answer 3

Ваш код имеет ошибку в логике расчета минимального веса еды. Кроме того, у вас есть опечатка в строке, которая инициализирует переменную n. Вместо n = a[0][0] должно быть n = a[0][p]. Я предлагаю вам следующую корректировку вашего кода:

b = list(map(int, input().split()))
a = []
for _ in range(b[0]):
    a.append(list(map(int, input().split())))

n = a[0][0]

# Используем двумерный массив dp для хранения минимального веса пути
dp = [[float('inf')] * b[1] for _ in range(b[0])]
dp[0][0] = a[0][0]

# Заполняем dp массив
for i in range(b[0]):
    for j in range(b[1]):
        if i > 0:
            dp[i][j] = min(dp[i][j], dp[i - 1][j] + a[i][j])
        if j > 0:
            dp[i][j] = min(dp[i][j], dp[i][j - 1] + a[i][j])

# Выводим результат
print(dp[b[0] - 1][b[1] - 1])

БЛОГ НА HUSL

помогите, пожалуйста, найти и исправить ошибку в коде

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