Jcxjdjjddj

Робот хочет перейти из правого нижнего угла поля размером N на M клеток ( 1 ≤ N , M ≤ 1000 ) в левый верхний. За один шаг он может переместиться на соседнюю клетку влево или на соседнюю клетку вверх. Кроме того, проходя через каждую клетку, Робот получает несколько золотых монет (это число известно для каждой клетки).
Определите, какое минимальное количество монет может собрать Робот по пути.

n,m=map(int, input().split())
a=[]
for i in range(n):
    a.append(list(map(int, input().split())))
dp=[[0] * m for i in range(n)]
dp[n-1][m-1]=a[n-1][m-1]
for i in range(n - 2, -1, -1):
    dp[i][m-1] = dp[i + 1][m - 1] + a[i][m - 1]
for j in range(m - 2, -1, -1):
    dp[n - 1][j] = dp[n - 1][j + 1] + a[n - 1][j]
for i in range(n - 2, -1, -1):
    for j in range(m - 2, -1, -1):
        dp[i][j] = min(dp[i + 1][j],dp[i][j+1])+ a[i][j]
print(dp[0][0])

Дана прямоугольная доска N × M (N строк и M столбцов). В правом верхнем углу находится шахматный конь, которого необходимо переместить нижний край доски (на нижнюю строку доски). При этом конь может ходить ТОЛЬКО на две клетки вниз и на одну клетку влево, либо на две клетки влево и на одну клетку вниз (смотри рисунок).

n, m = map(int, input().split())
dp = [[0] * m for i in range(n)]
dp[0][m - 1] = 1
for i in range(n):
    for j in range(m):
        if i - 1 >= 0 and j + 2 < m:
            dp[i][j] += dp[i - 1][j + 2]
        if i-2>=0 and j+1<m:
            dp[i][j]+=dp[i-2][j+1]
s = 0
for j in range(m):
    s+=dp[n-1][j]
print(s)

Робот хочет перейти из правого верхнего угла поля размером N на M клеток ( 1 ≤ N , M ≤ 1000 ) в левый нижний. За один шаг он может переместиться на соседнюю клетку влево или на соседнюю клетку вниз. Кроме того, проходя через каждую клетку, Робот получает несколько золотых монет (это число известно для каждой клетки).
Определите, какое максимальное количество монет может собрать Робот по пу

n, m = map(int, input().split())
a = []
for i in range(n):
    a.append(list(map(int, input().split())))
dp = [[0] * m for i in range(n)]
dp[0][m-1]=a[0][m-1]
for i in range(m-2,-1,-1):
  dp[0][i]=a[0][i]+dp[0][i+1]
for j in range(1,n):
  dp[j][m-1]=a[j][m-1]+dp[j-1][m-1]
for i in range(1,n):
  for j in range(m-2,-1,-1):
    dp[i][j]=a[i][j]+max(dp[i-1][j],dp[i][j+1])
print(dp[n-1][0])