Дано прямоугольное поле размером n*m клеток. Можно совершать шаги длиной в одну клетку вправо, или вниз, или по диагонали вниз и вправо(двигаться в других направлениях запрещено). Посчитать, сколькими способами можно попасть из левой верхней клетки в правую нижнюю. Решал методом динамического программирования, в интернете подобной задачи не нашел, только со стоимостью клеток, что не совсем то. Хочу проверить правильность своего решения. Для следующих размеров мои ответы:
- 1*3 - 1
- 4*3 - 19
- 25*24 - 32247603683099
- 7*4 - 167
Код следующий:
n,m = tuple(map(int, input().split(' ')))
res = [[0 for i in range(n)] for k in range(m)] # Заполнение поля нулями
for i in enumerate(res):
for k in enumerate(i[1]):
if (i[0] == 0) and (k[0] == 0): continue # В начальной точке кол-во маршрутов равно 0
if i[0] == 0:
res[0][k[0]] = 1 # В первой строке до любой клетки можно дойти только одним маршрутом из начала
elif k[0] == 0:
res[i[0]][0] = 1 # В первом столбце также до любой клетки только один маршрут из начала
else:
res[i[0]][k[0]] = res[i[0]-1][k[0]] + res[i[0]][k[0]-1] + 1 # Все остальные случаи вычисляются по формуле
# res[i][k] = res[i-1][k] + res[i][k-1] + 1
print(res[-1][-1])