algorithms – Time Complexity of Memoized Solution

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 ?