Я python не знаю... Но на С++ решение этой задачи - вот в этом ответе: https://ru.stackoverflow.com/a/770528/195342
Как видите, на ideone решило миллиард за 0.04с без особого напряжения по стеку.
Ключевые моменты:
- Перебор с отсечением
Мы сразу отсекаем особо длинные рекурсии, которые, очевидно, не приведут к оптимальному решению.
- Начинаем со значений, близких к корню
Такая вот эвристика - там цепочки самые короткие, и мы сразу найдем решение, которое позволит отсечь большое количество заведомо плохих решений и не лезть глубоко в рекурсии.
- Мемоизация
Позволит не считать повторно то, что уже посчитано. Кстати, подозреваю, что она не сильно и нужна, но сохранилась с предыдущих попыток решить задачу. Возможно, имеет смысл заменить массив, все-таки с немалым размером, на map
(словарь). Это уже надо проверять и экспериментировать, но увы, сегодня на это уже нет времени.
Да, это не так красиво выглядит... Но зато решает с очень малой глубиной рекурсии и очень быстро.
Еще раз извиняюсь за незнание python... Вроде у малого в школе на следующий год обещают его преподавать - ну, вот тогда придется изучить и исправиться :)
Update
Использовал вместо массива на миллиард байт просто map<int,unsigned char>
. На моей машине миллиард вместо 77ms стал считаться 104ms, но зато при этом потребовалось только 44675 элементов в map
. Экономию памяти оцените сами :)
При полном отказе от мемоизации не получается восстановить решение, но сама величина - 8 - для миллиарда находится за примерно 580ms.