Оптимизация отношения

Question

У меня есть рекуррентное отношение:

f(a,b) = f(a-1,b)+f(a-2,b-1)+f(a-1,b-1) 

, где ограничения: 1 <= a <= 10 ^ 9 и 1 <= b <= 1000.Я пытался использовать рекурсию, чтобы выяснить значения, но сложность времени была очень высокой.Я также попытался использовать таблицу dp, но она также имеет высокую временную сложность.Кроме того, поскольку a может быть до 10 ^ 9, невозможно создать такую ​​большую таблицу, поскольку сложность пространства будет слишком высокой, и я получу ошибку во время выполнения.Я хочу оптимизировать этот код, чтобы уменьшить его временную сложность.Может ли кто-нибудь помочь мне достичь этого?Я имею в виду, какую структуру данных использовать или какой алгоритм следует реализовать для достижения этой цели? </p>

Answer 1

Кстати, это лучший вопрос для CS StackExchange .Поскольку ваши переменные ограничены (в частности, b), мы можем трактовать f(a, b) как только одно число n, определенное как n=1000*a+b.Тогда a=n/1000 и b=n%1000.Определите новую функцию g(n)=f(a, b) на основе этого сокращения.Тогда мы имеем

g(n) = g(n-1000) + g(n-2001) + g(n-1001)

Используя стандартную формулу линейной повторяемости, получаем

g(n) = A*p^n + B*q^n + C*r^n

где p, qи r являются реальными решениями уравнения x^2001-x^1001-x^1000-1=0.Затем вы должны решить для A, B и C из начальных условий (то есть значения f(a, b), когда a и b невелики).Тогда у вас будет явная формула без необходимости рекурсии.Обратите внимание, что многочлен не очень численно стабилен, поэтому вам нужно быть осторожным в поиске корней.