I was solving Stone Game II on LeetCode. I was able to come up with a recursive (TLE) solution and was able to optimise the solution using memoization. The memoized solution is attached below.

```
class Solution {
int tSum(105) = {0};
public:
/**
* This method returns the maximum number of stones
* that can be collected where :
* - idx is the starting index
* - 2 * m is the maximum size of the window at idx
*/
int util(vector<int>& ar, vector<vector<int>> &dp, int idx, int m)
{
if(dp(idx)(m) != -1)
return dp(idx)(m);
if(idx + (2*m) - 1 >= ar.size())
{
int s = 0;
for(int i=idx; i<ar.size(); i++)
s += ar(i);
return dp(idx)(m) = s;
}
// Total number of stones from idx till the end
int total = idx > 0 ? tSum(ar.size()-1) - tSum(idx-1) : tSum(ar.size()-1);
int nStones = INT_MIN;
for(int i=0; i<(2*m) && (idx+i<ar.size()); i++)
{
// Best number of stones = total stones - best the other player can achieve
nStones = max(nStones, total - util(ar, dp, idx+i+1, max(m, i+1)));
}
return dp(idx)(m) = nStones;
}
int stoneGameII(vector<int>& ar) {
vector<vector<int>> dp(105, vector<int>(105, -1));
tSum(0) = ar(0);
for(int i=1;i<ar.size(); i++)
tSum(i) = tSum(i-1) + ar(i);
return util(ar, dp, 0, 1);
}
};
```

However, I am not sure about the time complexity of this solution.

According to me :

- There are
`m x n`

states, where :`n`

is the number of elements in`piles`

vector.`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`

i.e the size of`piles`

.

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 ?