Question

написать программу на питон: Количество маршрутов в прямоугольной таблице В прямоугольной таблице N×M вначале игрок находится в левой верхней клетке. За один ход ему разрешается перемещаться в соседнюю клетку либо вправо, либо вниз (влево и вверх перемещаться запрещено). Посчитайте, сколько есть способов у игрока попасть в правую нижнюю клетку. Входные данные Вводятся два числа N и M — размеры таблицы 1≤N≤10,1≤M≤10. Выходные данные Выведите искомое количество способов.

Answer 1

Так как речь идет о таблице, то лучше перебрать рекурсивно. Логично, что количество путей для клетки (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())

M = int(input())

print(calculate_max_way_price(0, 0, N, M))

Answer 2

Конечно, вот программа на Python, которая решает данную задачу с использованием динамического программирования:

pythonCopy code
def count_routes(N, M):
    # Создаем двумерный массив для хранения количества путей до каждой клетки
    dp = [[0] * M for _ in range(N)]
    
    # Инициализируем первую строку и первый столбец
    for i in range(N):
        dp[i][0] = 1
    for j in range(M):
        dp[0][j] = 1
    
    # Заполняем массив dp поочередно для каждой клетки
    for i in range(1, N):
        for j in range(1, M):
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
    
    # Возвращаем количество путей до правой нижней клетки
    return dp[N-1][M-1]

# Считываем размеры таблицы
N = int(input())
M = int(input())

# Вычисляем и выводим количество путей
result = count_routes(N, M)
print(result)

Пример использования:

yamlCopy code
Введите N: 3
Введите M: 4
Количество способов: 10

Просто введите значения N и M, и программа выведет количество способов добраться до правой нижней клетки.