关于这种递归关系的时间复杂度，在将其记忆后。

Question

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

有 2N 公司计划面试的人。飞行的费用 i-第1人到城市 A 是 costs[i][0]和飞行费用 i-第1人到城市 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 表，使用减法和征服递归法（由我们提供。本回答我得出了递归解的时间复杂度为 O(n) 哪儿 n 是指总人数(a=b=1 和 k=0).

然而，我不知道现在如何推导出时间复杂度，并加入了 dp 表。 我很困惑，因为，AFAIK，缓存的值会被使用多少次取决于具体的问题实例（值的 n 的大小，即 costs 表）。) 显然时间复杂度提高了（因为我们已经缓存了重叠子问题的结果）不是吗？

谁能指出这是什么原因？

谢谢!

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

Answer 1

作为一个几乎可以一直依赖的经验法则，DP的时间复杂度是O(DP表的大小*O(过渡))。这是因为你可以假设得到DP表的内存本身就是时间，更不用说在大多数情况下，你会有可能访问所有这些状态。对于大多数问题来说，如果你在给定最坏情况的输入下，没有系统性地访问你的大多数状态，你的状态可以被减少。但我离题了。

对于这个特定的问题，你的运行时间将是O(cost.size()^2)，因为你的过渡看起来是O(1)，你的备忘表是O(cost.size()^2)

此外，只是一个很好的事情，我喜欢做的是。return dp[i][j]=minVal. 而在一般情况下。return dp[state] = returnval 是很有帮助的，因为你知道你没有忘记记忆。祝您好运!