Как вычислить кратчайшую цепочку сложения для произвольного n <= 600 за одну секунду?

Как за одну секунду вычислить кратчайшую цепочку сложения (sac)для произвольного n

Примечания

Это соревнование по программированию на codility в этом месяце.

Цепочки сложения очень важны в численном отношении, поскольку они представляют собой наиболее экономичный способ вычисления x^n (последовательными умножениями ).

В книге Кнута Art of Computer Programming, Volume 2, Seminumerical Algorithms есть хорошее введение в цепочки сложения и некоторые интересные свойства, но я не нашел ничего, что позволило бы мне выполнить строгие требования к производительности.

Что я пробовал (спойлер)

Во-первых, я построил (сильно разветвленное)дерево(с началом 1-> 2 -> (3 ->..., 4 ->... ))такие, что для каждой вершины n путь от корня к n является мешком для n. Но при значениях >400 время работы примерно такое же, как при приготовлении кофе.

Затем я использовал эту программу, чтобы найтинекоторые полезные свойства для сокращения пространства поиска. Благодаря этому я могу собрать все решения до 600, пока варю кофе. Но для n мне нужно вычислить все решения до n. К сожалению, codility также измеряет время выполнения инициализации класса...

Поскольку проблема вероятно, NP-hard , я закончил hard-кодированием таблицы поиска . Но так как codility попросили сконструировать мешок, я не знаю, имели ли они в виду справочную таблицу, поэтому я чувствую себя грязным и похожим на мошенника. Отсюда этот вопрос.

Обновление

Если вы считаете, что жестко-закодированная полная таблица поиска — это то, что вам нужно,Можете ли вы привести аргумент, почему вы думаете, что полное вычисление/частично вычисленные решения/эвристика не будут работать?