Так как речь идет о таблице, то лучше перебрать рекурсивно. Логично , что количество путей для клетки (i,j) - это количество путей для правой соседней клетки + количество путей для нижней соседней клетки.
При таком условии мы будем посещать те же клетки слишком часто, однако значение для них меняться не будет. Имеет смысл вычислить их единожды и запомнить для последующих использований. (На самом деле, достаточно иметь буфер вместимостью всего в 6 элементов, но мы сделаем полное запоминание).
(Иллюстрация 3 - таблица кэша)
Иллюстрации кода и возможного вывода прикреплены в дополнительных материалах.
========================
Ваши оценки и отзывы позволяют лучше оценить качество ответа.
Если ответ удовлетворил, не забудь отметить его как "Лучший".
Успехов в учёбе!
========================
Код:
cache = {}
def calculate_max_way_price(x: int, y: int, m:int, n:int):
if (x, y) in cache:
return cache[(x, y)]
x_way, y_way = 0, 0
if x < m - 1:
x_way = calculate_max_way_price(x + 1, y, m, n)
if y < n - 1:
y_way = calculate_max_way_price(x, y + 1, m, n)
if x == m - 1 and y == n - 1:
cache[(x, y)] = 1
return 1
cache[(x, y)] = x_way + y_way
return x_way + y_way
N = int(input("Enter N value: "))
M = int(input("Enter M value: "))
print(calculate_max_way_price(0, 0, N, M))
Ей, жарық күн, нұрыңды шаш далама,
шаш нұрыңды қарттарға, жас балаға,
ызғар сіңген жеріме шуақ керек,
мұқтаж оған ауыл да, астана да.
Сәулеңменен себеле үміт демін,
жер бетінен жылыссын күдіктерім.
Адамдардың сатқындық, сұмдығынан
қалжыраған жерімді жібіт менің.
Күңгірттенбей, көтерсін шыңым басын,
қарттарымның ұзартқын ғұмыр жасын.
Қорқыныш пен үрей жер кеуделерде,
қу бәрін де — соңына бұрылмасын!
Кетсін тағы шарықтап алысқа үнім,
қонақтасын ырыс пен табыс күнім.
Ұл-қыздары көтерсін қол ұстасып
қазағымның елдік пен намыс туын.
Жарқырасын шуақ боп алғашқы үміт,
жүректерді жүрекпен жалғастырып.
Адамзатқа бірлік бер, тыныштық бер –
ынтымақтан туындар бар жақсылық!