Так как речь идет о таблице, то лучше перебрать рекурсивно. Логично , что количество путей для клетки (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))
Объяснение:
Мы находим функции прямых, ограничивающих область (по точкам).
Эти прямые дают координаты Y точки по её координате X.
Если некая y = f(x) в точке X0 принимает Y0 и это соответствует введенным значениям, то введенная точка лежит на прямой.
Но нам интересны значения в области. Если введенное значение Y больше рассчитанного Y0, то (X; Y) находится выше прямой y = f(x).
Если же меньше рассчитанного, то ниже.
Смотря на рисунок мы определяем, какие прямые у нас имеются, и где должна быть точка, чтобы находиться внутри области: выше или ниже прямых, ограничивающих область (для каждой прямой).
Потом переносим это в виде условия.
Пример на Python:
def get_line_by_two_points(x0: float, y0: float, x1: float, y1: float):
def line_y(x: float):
return (x - x0)/(x1 - x0) * (y1 - y0) + y0
return line_y
l1 = get_line_by_two_points(-3, 7, -6, 1) # Левая наклонная
l2 = get_line_by_two_points(7, 1, 4, 7) # Правая наклонная
x_value = int(input("Enter an X value: "))
y_value = int(input("Enter a Y value: "))
if 1 < y_value < 7 and y_value < l1(x_value) and y_value < l2(x_value):
print("Point is in the space!")
else:
print("Point is NOT in the space!")