leedcode1376题class Solution {public: int numOfMinutes(int n, int headID, vector<int>& manager, vector<int>& informTime) { int res = 0; // 遍历下属，找到下属中需要花费时间最长的那一个 for (int i = 0; i < n; i++) { if (manager[i] == headID) { res = max(res, numOfMinutes(n, i, manager, informTime)); } } // 加上当前领导向下属传递信息所需要的时间 return res + informTime[headID]; }};代码超出时间限制，如何优化

这个问题的核心在于遍历下属的过程，因为遍历下属是一个递归过程，所以在遍历过程中会有很多重复计算，导致算法时间复杂度较高。可以使用记忆化搜索来优化算法，缓存已经计算过的结果，避免重复计算。

具体来说，可以使用一个数组来记录每个员工的最长传递时间，如果已经计算过该员工的最长传递时间，直接返回该值，否则就递归计算该员工的最长传递时间。

优化后的代码如下：

class Solution {
public:
    int numOfMinutes(int n, int headID, vector<int>& manager, vector<int>& informTime) {
        vector<int> memo(n, -1); // 缓存每个员工的最长传递时间
        return dfs(headID, manager, informTime, memo);
    }

    int dfs(int cur, vector<int>& manager, vector<int>& informTime, vector<int>& memo) {
        if (memo[cur] != -1) { // 如果已经计算过该员工的最长传递时间，直接返回该值
            return memo[cur];
        }
        int res = 0;
        for (int i = 0; i < manager.size(); i++) {
            if (manager[i] == cur) { // 遍历当前员工的下属
                res = max(res, dfs(i, manager, informTime, memo)); // 递归计算下属的最长传递时间
            }
        }
        memo[cur] = res + informTime[cur]; // 更新缓存
        return memo[cur];
    }
};

这样，时间复杂度就从指数级别降到了线性级别，可以通过本题。