Beating naive dynamic programming: examples similar to integer partitions?
One nice example is the Hamiltonian Path problem is easily solvable in $O(2^n(n+m))$ time (Bellman, 1962) by dynamic programming over vertex subsets. In 2010 Björklund gave an algorithm running in time $O(1.657^n)$ using determinants and polynomial identity testing in a field of characteristic $2$.

Another example is that of “connectivity problems”, such as Hamiltonian Path, Steiner Tree, or Feedback Vertex Set on graphs of treewidth $k$. The naive dynamic programming algorithms for these problems run in time $2^{O(k \log k)}n^{O(1)}$, and at a glance it really looks like that is what the ``correct’’ running time for these problems should be. However, in a wonderful paper, Cygan et al. showed that these problems all allow algorithms with running time $2^{O(k)}n^{O(1)}$, again cleverly using polynomial identity testing in a field of characteristic 2.