Задача Python. Буду очень благодарен если решите Написать код программы: Кладоискатель хочет перейти из левого верхнего угла поля размером N на M клеток в правый нижний. За один шаг он может переместиться на соседнюю клетку вправо или на соседнюю клетку вниз. Поле заполнено золотыми монетами, которые можно забрать по пути. Количество монет в каждой клетке поля известно. Определите путь, по которому должен пройти кладоискатель, чтобы он смог собрать как можно больше монет. Выведите это количество.

Предыдущий
вопрос Следующий
вопрос

Для решения данной задачи можно воспользоваться динамическим программированием. Ниже представлен код программы на Python, который находит путь с максимальной суммой монет:

def find_maximum_coins_path(N, M, coins):
dp = [[0 for _ in range(M)] for _ in range(N)]
for i in range(N):
for j in range(M):
if i == 0 and j == 0:
dp[i][j] = coins[i][j]
elif i == 0:
dp[i][j] = dp[i][j-1] + coins[i][j]
elif j == 0:
dp[i][j] = dp[i-1][j] + coins[i][j]
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + coins[i][j]
path = []
i, j = N-1, M-1
while i > 0 or j > 0:
path.append((i, j))
if i == 0:
j -= 1
elif j == 0:
i -= 1
elif dp[i-1][j] > dp[i][j-1]:
i -= 1
else:
j -= 1
path.append((0, 0))
path.reverse()
return dp[N-1][M-1], path
# Пример использования
N = 3
M = 4
coins = [
[1, 2, 3, 4],
[5, 6, 7, 8],
[9, 10, 11, 12]
]
max_coins, path = find_maximum_coins_path(N, M, coins)
print("Максимальное количество монет:", max_coins)
print("Путь с максимальным количеством монет:")
for i, j in path:
print(f"({i}, {j}) ->", end=" ")

Программа принимает на вход размеры поля N и M, а также двумерный массив coins, содержащий количество монет в каждой клетке поля. Далее программа использует динамическое программирование для нахождения пути с максимальной суммой монет и выводит этот путь, а также общее количество монет, которое удалось собрать кладоискателю.