Условие задачи
В левом верхнем углу прямоугольной таблицы размером n × m находится черепашка. Она хочет попасть в правый нижний угол к своей любимой семье. У неё есть своя особенность: черепашка умеет ходить лишь вправо, либо вниз.
За нахождение в клетке, находящейся на пересечении i-й строки и j-го столбца, на черепашку накладывается штраф в размере aij рублей. Естественно, черепашка хочет дойти до семьи с минимальным суммарным штрафом. Помогите ей сделать это.
Алгоритм решения
Задача решается с помощью динамического программирования:
Создаем массив d. Тогда в ячейке d[i][j] - хранится минимальная сумма штрафа, которую мы соберем по дороге от [0,0] ячейки в ячейку [i,j].
Соответственно, сам ответ будет храниться в ячейке d[n][m]
Заполняем каждую ячейку с помощью проверки сумм:
d[i][j] = min(d[i-1][j],d[i][j-1])+d[i][j] - минимальная сумма из предыдущей верхней или левой ячейки + сама сумма данной ячейки (так как черепашка ходит только вниз и влево).
Код программы
import sys
n,m = map(int,input().split())
a = [list(map(int,input().split())) for i in range(n)]
for i in range(n):
for j in range(m):
if j==0 and i!=0:
a[i][j]+=a[i-1][j]
if i==0 and j!=0:
a[i][j]+=a[i][j-1]
if i>0 and j>0:
a[i][j]=min(a[i-1][j],a[i][j-1])+a[i][j]
print(a[n-1][m-1])
Задача не сложная, остались вопросы - пиши в комментариях!
#информатика #программирование #егэ по информатике #программирование на питон