Optimizing the problem I have a recurrence relation:

$$f(a,b) = \begin{cases}
  1 &amp; (a,b) = (0, 0)\\
  1 &amp; (a,b) = (a, 0)\\
  0 &amp; (a,b) = (0, b)\\
  2a &amp; (a,b) = (a,1)\\
  f(a-1,b) + f(a-2, b-1) + f(a-1,b-1) &amp; \mathrm{otherwise}
\end{cases}$$

Where the constraints: $1 \leq a \leq 10^9$ and $1 \leq b \leq 1000$. I tried using recursion to find out the values but the time complexity was very high. I also tried using a dp table but that has a high time complexity as well. Also, since a can be upto $10^9$, it isn't possible to create such a large table as the space complexity will be too high and I'll get a runtime error. I want to optimize this code so that its time complexity gets reduced. Can anyone help me to achieve this? I mean which data structure to use or what algorithm should I implement to achieve this?
you can go to Dynamic programming. To achieve benefits do this you need overlapping recursion.

Easiest way yo program it, using a Map library as Memoization. Store any value calculated. Check any value from the map before calculation. This will eliminate the recalculations.

The simple case is always the Fibonacci Sequence, in which given $n$ find the $F(n) = F(n-1) + F(n-2)$.

You could see the overlappings easily. Make an array to store $F_i$ once found to prevent refound, Top-Down.

Buttom up; Start from the lowest of the recursion to reach the target. 

For your case you need a table of size $10^9 \times 1000$ to fill. If the size is big, you may reuse some rows.