Решение повторения типа Фибоначчи за log n времени

Нахождение n-го члена в ряду Фибоначчи f (n) = f (n-1) + f (n-2) может быть решено за O (n) раз с помощью запоминания.

Более эффективным способом было бы найти n-ю степень матрицы [[1,1], [1,0]] с помощью функции «разделяй и властвуй» для решения Фибоначчи за log n времени.

Есть ли аналогичный подход, которому можно следовать для f (n) = f (n-1) + f (n-x) + f (n-x + 1) [x - некоторая константа].

Просто сохраните предыдущие x элементов, это можно решить за O (n) раз.

Есть ли лучший способ решить эту рекурсию.