from time import monotonic_ns
import matplotlib.pyplot as plt


def main():
    b = []
    for i in range(100, 500):
        t = monotonic_ns()
        f = grid_traveler(i, i)
        t = monotonic_ns() - t
        c = t / (i*i)
        b.append(c)
    plt.plot(b)
    plt.show()


# Вычисляет, сколько путей есть из левого верхнего угла в правый нижний,
# при высоте n и ширине m. Двигаться можно только вправо и вниз единичными шагами
def grid_traveler(n: int, m: int, memo=None) -> int:
    if memo is None:
        memo = {}
    if n == 1 or m == 1:
        return 1
    if (key := (min(n, m), max(n, m))) not in memo:
        memo[key] = grid_traveler(n - 1, m, memo) + grid_traveler(n, m - 1, memo)
    return memo[key]


if __name__ == '__main__':
    main()