My question is inspired by the following problem:
Given $k$ coins with denominations $\{c_1, ..., c_k\}$, how many ways are there to generate $n$ cents?
This can be solved in $\Theta(nk)$ time using dynamic programming. But can also be solved by finding the coefficient of $x^n$ in the generating function $\prod_{i \leq k} \frac{1}{1-x^{c_i}}$
What is the time complexity of such an approach?
How is the time complexity related to which generating function is solved for?
If you're willing to make the complexity worse in $k$ you can make it substantially better in $n$. Suppose we want to extract the coefficient $a_n$ of $x^n$ in the generating function $\frac{P(x)}{Q(x)}$ where $Q$ is a polynomial of degree $d$ with nonzero constant term and $\deg P < \deg Q$. Then, as it turns out, we can write down a $d \times d$ matrix $M$ (the companion matrix of the polynomial whose coefficients are the reverse of $Q$'s) and vectors $v, w$ such that $$a_n = v^T M^n w.$$
So the problem reduces to the efficient computation of powers of a matrix, and this can be done efficiently by binary exponentiation. This uses $O(\log n)$ matrix multiplications, but unfortunately the sizes of the entries in general grow exponentially in $n$.
However, in this case the sizes of the entries grow polynomially in $n$, so the final time complexity is polynomial in both $d$ and $\log n$.
Example. Let $\frac{P(x)}{Q(x)} = \frac{x}{1 - x - x^2}$ be the generating function for the Fibonacci numbers $F_n$. Then, as it turns out, the matrix we want is $M = \left[ \begin{array}{cc} 1 & 1 \\\ 1 & 0 \end{array} \right]$, and it satisfies $$M^n = \left[ \begin{array}{cc} F_{n+2} & F_{n+1} \\\ F_{n+1} & F_n \end{array} \right].$$
The binary exponentiation strategy above corresponds to repeated use of the duplication formulas $$F_{2n} = F_{n+1}^2 + F_n^2$$ $$F_{2n+1} = F_{n+2} F_{n+1} + F_{n+1} F_n$$
both of which follow directly from the identity $M^{2n} = (M^n)^2$.
I should also mention that for fixed $k$ you can in fact write down an explicit quasi-polynomial closed form for the answer, so you just need an efficient algorithm for integer multiplication.