I was solving Stone Game II on LeetCode. I was able to come up with a recursive (TLE) solution, which I optimized using memoization. The recursive solution computes a function $u(i,m)$, depending on an array $A_1,\ldots,A_n$, where:
- $i$ is the starting index
- $2m$ is the maximum size of the window at $i$
Here is the recurrence: $$ u(i,m) = \begin{cases} \sum\limits_{j=i}^{n} A_j & \text{if } i + 2m-1 > n, \\ \sum\limits_{j=i}^{n} A_j - \min\limits_{\substack{0 \leq k \leq 2m-1 \\ i+k \le n}} u(i+k+1, \max(m,k+1)), & \text{if } i + 2m-1 \le n. \end{cases} $$ (Using $O(n)$ preprocessing, the sums can be computed in $O(1)$.)
I am interested in the value of $u(1,1)$.
However, I am not sure about the time complexity of this solution.
According to me :
- There are $m \times n$, where:
- $n$ is the number of elements in $A$.
- $m$ is the width of window that varies at each step.
- Each state is being calculated only once.
- $m$ can not be greater than $n$, the size of $A$.
Hence, the time complexity of the solution should be $O(n^2)$.
Is there something that I am missing? Is there a mathematical way to prove this?