Python, количество путей по обходу матрицы, проверяющая система пишет, что при запуске кода происходит ошибка выполнения

Рейтинг: 0Ответов: 1Опубликовано: 28.07.2023

я написала код по следующей задаче:

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

Поскольку количество способов, которое нужно найти, может быть очень велико, 
вычислите его по модулю 10 6 + 7 , то есть найдите остаток от деления этого 
числа на 10 6 + 7 .

Входные данные
Входная строка содержит два натуральных числа: размеры поля N и M , 
разделённые пробелом ( 1 ≤ N , M ≤ 1000 ).

Выходные данные
Программа должна вывести одно число: количество различных маршрутов 
из левого верхнего угла поля в правый нижний по модулю 10 6 + 7 .

Примеры
входные данные
20 20
выходные данные
16385

Написала по ней код:

n, m=map(int, input().split()) 
a=[[1]*m for i in range(n)]
for i in range(1, n):
    for j in range(1, m):
        a[i][j]=a[i-1][j]+a[i][j-1] 
print((a[n-1][m-1])%(10**6+7))

Но на 4 последних тестах проверяющей системы написано "ошибка выполнения программы" (об ошибке больше ничего не написано), помогите пожалуйста понять, что это за ошибка и исправить код!!!

python алгоритм динамическое-программирование
Источник: Stack Overflow на русском

Ответы

▲ 2Принят

Чтобы гигантские числа в расчётах не участвовали, взятие остатка применяйте при каждом сложении:

 a[i][j]=(a[i-1][j] + a[i][j-1]) % 1000007

Кроме того, в расчетах всегда участвует только текущая и предыдущая строка, поэтому хранить всю таблицу не обязательно, а можно выделить память под пару строк, переключая их по чётности индекса:

n, m=map(int, input().split())
a=[[1]*m for i in range(2)]
for i in range(1, n):
    last = (i + 1) % 2
    current = i % 2
    for j in range(1, m):
        a[current][j]=(a[last][j] + a[current][j-1]) % 1000007
print(a[(n-1)%2][m-1])