Тема: Оптимізація програми
Доброго дня! Дуже потрібна допомога з однією задачею з теми "Динамічне програмування" на сайті e-olymp.com
Мишка і зернинки
В індійському храмі підлогу прямокутної форми вимощено однаковими квадратними плитками 1 x 1, на кожну з яких насипано від 0 до k зернинок (k ≤ 30000). Розміри підлоги m х n. Мишка вибігає з лівого нижнього кута підлоги храму i рухається до входу у іншу нірку, розміщену у протилежному кутку. Мишка може рухатись лише праворуч або вперед, збираючи всі зернинки з плитки, на якій вона знаходиться. Знайти маршрут, рухаючись по якому мишка збере найбільшу кількість зернин.
Вхідні дані
Перший рядок містить числа m та n - розміри підлоги (1 ≤ m, n ≤ 100). Далі йде m рядків, починаючи з верхнього, у кожному з яких розміщено n чисел – кількість зернинок на відповідній плитці.
Вихідні дані
Вивести маршрут руху мишки у форматі: RRFFFRF (F - крок вперед, R - крок праворуч).
Мій розв'язок наступний:
a,b=[int(i) for i in input().split()]
c=[]
for i in range(a):
c=c+[[int(i) for i in input().split()]]
x=0
y=a-1
res=""
for i in range(1, b):
c[y][i]=c[y][i]+c[y][i-1]
for i in range(y-1,-1,-1):
c[i][x]=c[i][x]+c[i+1][x]
for i in range(y-1,-1,-1):
for j in range(1,b):
c[i][j]=c[i][j]+max(c[i+1][j],c[i][j-1])
for i in range(a):
c[i]=c[i][::-1]
c=c[::-1]
while True:
if y==0 and x==b-1:
break
elif y==0:
x=x+1
res=res+'R'
elif x==b-1:
y=y-1
res=res+'F'
elif c[y][x+1]>c[y-1][x]:
x=x+1
res=res+'R'
elif c[y][x+1]<c[y-1][x]:
y=y-1
res=res+'F'
print(res[::-1])На скільки я зрозумів, сам розв'язок правильний, але великі матриці обробляє занадто довго. Як мені оптимізувати дану програму, можливо є простіший алгоритм? Але, я поки що вмію тільки так))) Допоможіть будь-ласка!
