Time Complexity of Memoized Solution
For each $i,m$ in the range $n/3 \leq i,m \leq 2n/3$, computing the recurrence requires going over $\Theta(n)$ values of the parameter $k$, hence calculating $u(i,m)$ for all of these values of $i,m$ requires time $\Theta(n^3)$.
Do you actually encounter such values of $i,m$ when calculating $u(1,1)$? It's not immediately clear to me, but you'll have to rule it out if you want to prove a better upper bound on the running time of your procedure.