About time complexity of this recurrence relation after memoizing it

Question

I solved a question on LeetCode.com with some online help:

There are 2N people a company is planning to interview. The cost of flying the i-th person to city A is costs[i][0], and the cost of flying the i-th person to city B is costs[i][1]. Return the minimum cost to fly every person to a city such that exactly N people arrive in each city.

as:

class Solution {
public:
    int helper(vector<vector<int>>& c, vector<vector<int>>& dp, int start, int a, int b) {
        if((a>c.size()/2) || (b>c.size()/2)) return INT_MAX/2;
        if(a+b==(int)c.size()) return 0;
        
        if(dp[a][b]!=-1) {
            return dp[a][b];
        }
        
        int minA=c[start][0]+helper(c, dp, start+1, a+1, b);
        int minB=c[start][1]+helper(c, dp, start+1, a, b+1);

        int minVal=min(minA, minB);
        dp[a][b]=minVal;
        
        return minVal;
    }
    
    int twoCitySchedCost(vector<vector<int>>& costs) {
        vector<vector<int>> dp(costs.size()+1, vector<int>(costs.size()+1, -1));
        int minCost=helper(costs, dp, 0, 0, 0);
        
        return minCost;
    }
};

Without the dp table, using the Subtract-and-Conquer Recurrence method (courtesy of this answer, I came up with the time complexity of the recursive solution as O(n) where n is the total number of people (a=b=1 and k=0).

However, I am unsure how to derive the time complexity now, with the inclusion of the dp table. I am confused because, AFAIK, how many times the cached values would be used depends upon the specific problem instance (value of n i.e., the size of the costs table). Obviously the time complexity has improved (since we have cached the results of the overlapping sub-problems) hasn't it?

How can I derive this?

Edit

As I notice this again, I realize that I made a mistake in calculating the time complexity above - my a is not 1, it is 2. Which brings the time complexity to be O(2^n).

Answer 1

As a rule of thumb that you can almost always rely on, the time complexity of a DP is O(size of DP Table * O(transition)). This is because you can assume getting the memory for your DP Table is time itself, not to mention the fact that you, in most cases, would have the possibility to visit all of those states. For most problems, if you don't visit a systematic majority of your states given worst-case input, your state can be reduced. But I digress.

For this specific problem, your runtime would be O(costs.size()^2), since your transition looks O(1) and your memo table is O(costs.size()^2)

Also, just a nice thing that i like to do is return dp[i][j]=minVal. And in general, return dp[state] = returnval is helpful because you know you didn't forget to memoise. Best of luck!