Завершение функции, которая не должна ничего возвращать (Задача 169 на ACMP)

Question

StackOverFlow. Я так много раз порывался написать свой первый вопрос, но всегда находил ответ. Если разместил что-то не туда или не так, прошу простить: не опытен, исправлюсь.

Задача:

На расстоянии n шагов от магазина стоит человек. Каждую секунду он выбирает, куда сделать шаг: к магазину или в противоположном направлении. Напишите программу, которая определит, сколькими способами он может попасть в магазин, пройдя ровно k шагов и оказавшись в магазине только после выполнения последнего шага.

На вход подаются через пробел два целых числа n – расстояние до магазина в шагах и k – требуемое количество шагов, которые должен сделать человек (1 ≤ n ≤ k ≤ 50).

На выход следует подать только одно число - количество способов попадания в магазин.

Имею функцию такого рода:

i = input().split()
shop = int(i[0])
count = int(i[1])
ans = 0

def p(c, shop):
    #print(c, shop)
    global ans
    if shop == c - 2:
        ans += shop
        #print('here')
        return None
    elif shop == 0:
        #print('no here')
        return 0
    else:
        return p(c-1, shop - 1), p(c-1, shop + 1)

a = p(count, shop)
print(ans)

Могу ли я не возврашать ничего каким-то более экономичным способом в плане количества операций, которые делает процессор? Дорогая ли операция возврата, может дешевле возвращать число или что-то другое? Функция разворачивается в огромные деревья, а уменя ограничение всего 1 секунда.

Могу ли я не использовать каким-то образом в такой задаче глобальную переменную.

Я попытался найти ответ на свой вопрос здесь и в гугле, но максимум нашел вопрос по С, может ли функция не иметь return. Я знаю, что может, но мне нужен, некий аналог break, который тут не работает.

Большое вам спасибо.

UPD. Обновил вопрос, по просьбам в комментариях. UPD2. В финальной версии программы все вопросы уже и не актуальны. Первый блин комом.

Answer 1

Извините, я смог сам найти ответ. Тут нужно было использовать мемоизацию, что весьма очевидно, но я только начинаю изучать динамическое программирование.

i = input().split()
shop = int(i[0])
count = int(i[1])
memory = []
for _ in range(count):
    memory.append([0]* (count))
def p(count, shop):
    if count == shop:
        return 1
    if count == shop+2:
        return shop
    else:
        b = pp(count, shop)
        return b

def pp(count, shop):
    global memory
    #print(count, shop)
    if shop == 0 or shop > count:
        #print('here 0')
        return 0
    if memory[count-1][shop-1] == 0:

        if shop == count - 4:
            #print('here umn')
            s = int((shop+3) * (shop/2))
            memory[count-1][shop-1] = s
            return s
        else: 
            s = pp(count-1, shop+1) + pp(count-1, shop-1)
            memory[count-1][shop-1] = s
            return s
    else:
        return memory[count-1][shop-1] 
a = p(count, shop)
print(a)
#print(memory)

БЛОГ НА HUSL

Завершение функции, которая не должна ничего возвращать (Задача 169 на ACMP)

Ответы (1 шт):