关于这个递归关系记忆后的时间复杂度

Question

我在 LeetCode.com 上通过在线帮助解决了一个问题：

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.

如：

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 table 的情况下，使用 Subtract-and-Conquer Recurrence 方法（由 this answer 提供，我得出递归解决方案的时间复杂度为 O(n) 其中 n 是总人数（a=b=1 和 k=0）。

但是，我不确定现在如何推导出包含 dp table 的时间复杂度。我很困惑，因为据我所知，缓存值的使用次数取决于具体的问题实例（n 的值，即 costs table 的大小）。显然时间复杂度有所提高（因为我们缓存了重叠子问题的结果）不是吗？

我如何得出这个？

编辑

当我再次注意到这一点时，我意识到我在计算上面的时间复杂度时犯了一个错误——我的 a 不是 1，而是 2。这使得时间复杂度为 O(2^n).

Answer 1

作为您几乎总是可以依赖的经验法则，DP 的时间复杂度是 O（DP 的大小 Table * O（转换））。这是因为您可以假设为您的 DP Table 获取内存本身就是时间，更不用说在大多数情况下您将有可能访问所有这些状态。对于大多数问题，如果您在给定最坏情况输入的情况下没有系统地访问大多数状态，则可以减少您的状态。但是我跑题了。

对于这个特定问题，你的运行时间是 O(costs.size()^2)，因为你的转换看起来是 O(1) 而你的备忘录 table 是 O(costs.size()^2)

此外，我喜欢做的一件好事是 return dp[i][j]=minVal。通常，return dp[state] = returnval 很有用，因为您知道自己没有忘记记忆。祝你好运！

关于这个递归关系记忆后的时间复杂度

About time complexity of this recurrence relation after memoizing it

c++

algorithm

memoization

dynamic-programming

time-complexity

编辑