Let $p(n)$ denote the number of partitions of $n\in\mathbb{N}$ (briefly, number of ways to split a pile of $n$ stones into $\geq1$ unordered nonempty parts). The classical dynamic programming algorithm to find $p(n)$ is to construct a square table $A$ where $$A_{i,j} = \text{partitions of $i$ where each part is $\leq j$}$$ and recursively fill it using the rules $$A_{i,j} = A_{i,j-1} \text{ if }j>i$$ and $$A_{i,j} = A_{i,j-1} + A_{i-j,j}\text{ otherwise}$$ with the appropriate conventions for the corner cases. Then $p(n)=A_{n,n}$. This takes $O(n^2)$ operations on integers (let's say we're looking for $p(n)$ modulo some big number, so the size of the numbers is $O(1)$). We can optimize the memory down to $O(n)$ by noticing that we only need the previous column to find the next one.
However, the pentagonal number theorem due to Euler says that $$p(n) = \sum_{k\in\mathbb{Z}:g_k\leq n}(-1)^{k+1}p(n-g_k)$$ where $g_k = k(3k-1)/2$ are the pentagonal numbers. This allows us to recursively build a one-dimensional list of the $p(i)$, using only $O(n\sqrt{n})$ operations, since the above sum contains $O(\sqrt{n})$ terms.
My question: I was wondering if there are other examples of natural problems for which there is such a surprising speed-up over the standard dynamic programming algorithm, or if this is more of an isolated case complexity-wise.
