关于记忆后这种递归关系的时间复杂性

我解决了一个问题 LeetCode.com 有一些在线帮助:

有 2N 公司计划面试的人。乘坐飞机的费用 i -第人进城 A 是 costs[i][0] ,以及飞行的成本 我 -第人进城 B 是 costs[i][1] .返回每个人飞往城市的最低费用,以便准确 N 人们来到每个城市。

如:

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;
    }
};

没有 dp 表,使用减法和征服递归方法(由 this answer ,我提出了递归解的时间复杂度 O(n) 哪里 n 是总人数( a=b=1 和 k=0 ).

然而,我不确定现在如何得出时间复杂度,包括 dp 桌子。我感到困惑,因为AFAIK,缓存值的使用次数取决于具体的问题实例(值 n 即 costs 桌子)。显然,时间复杂度有所提高(因为我们缓存了重叠子问题的结果),不是吗?

我怎么能得出这个?

编辑

当我再次注意到这一点时,我意识到我在计算上述时间复杂度时犯了一个错误——我的 a 不是 1 ,它是 2 这就带来了时间的复杂性 O(2^n) .