Medium

题目描述

有一项包含 n 个问题的调查，每个问题的答案要么是 0（否），要么是 1（是）。

这项调查分别给了 m 个学生（编号从 0 到 m - 1）和 m 个导师（编号从 0 到 m - 1）。学生的答案用二维整数数组 students 表示，其中 students[i] 是一个整数数组，包含第 i 个学生的答案（下标从 0 开始）。导师的答案用二维整数数组 mentors 表示，其中 mentors[j] 是一个整数数组，包含第 j 个导师的答案（下标从 0 开始）。

每个学生都会被分配给一个导师，每个导师也都会有一个学生分配给他们。学生-导师配对的兼容性评分等于学生和导师答案相同的题目数量。

  • 例如，如果学生的答案是 [1, 0, 1] 而导师的答案是 [0, 0, 1]，那么他们的兼容性评分为 2，因为只有第二个和第三个答案相同。

你的任务是找到最优的学生-导师配对方案，使兼容性评分的总和最大。

给定 students 和 mentors，返回可以实现的最大兼容性评分总和。

示例 1：

输入：students = [[1,1,0],[1,0,1],[0,0,1]], mentors = [[1,0,0],[0,0,1],[1,1,0]]
输出：8
解释：我们按以下方式为学生分配导师：
- 学生 0 分配给导师 2，兼容性评分为 3。
- 学生 1 分配给导师 0，兼容性评分为 2。  
- 学生 2 分配给导师 1，兼容性评分为 3。
兼容性评分总和为 3 + 2 + 3 = 8。

示例 2：

输入：students = [[0,0],[0,0],[0,0]], mentors = [[1,1],[1,1],[1,1]]
输出：0
解释：任何学生-导师配对的兼容性评分都是 0。

约束条件：

  • m == students.length == mentors.length
  • n == students[i].length == mentors[j].length
  • 1 <= m, n <= 8
  • students[i][k] 要么是 0 要么是 1
  • mentors[j][k] 要么是 0 要么是 1

解题思路

这是一个经典的分配问题，需要找到最优的学生-导师一对一匹配。

思路分析：

由于约束条件中 m ≤ 8，数据规模较小，我们可以考虑以下几种解法：

  1. 回溯法（推荐）：通过递归尝试所有可能的分配方案。对于每个学生，尝试分配给每个还未被分配的导师，然后递归处理下一个学生。

  2. 状态压缩动态规划：使用位掩码表示哪些导师已被分配，dp[mask] 表示当前导师分配状态下的最大兼容性评分。

  3. 全排列枚举：生成所有可能的学生-导师配对排列，计算每种配对的总评分。

核心步骤：

  1. 预计算每个学生与每个导师的兼容性评分（相同答案的数量）
  2. 使用回溯法枚举所有可能的分配方案
  3. 对每种完整的分配方案，计算总评分并更新最大值

优化要点：

  • 预计算兼容性矩阵避免重复计算
  • 使用位操作优化导师使用状态的管理
  • 剪枝：如果当前部分解加上剩余最大可能评分仍小于已知最优解，则提前返回

代码实现

class Solution {
public:
    int maxCompatibilitySum(vector<vector<int>>& students, vector<vector<int>>& mentors) {
        int m = students.size(), n = students[0].size();
        
        // 预计算兼容性评分矩阵
        vector<vector<int>> scores(m, vector<int>(m));
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < m; j++) {
                for (int k = 0; k < n; k++) {
                    if (students[i][k] == mentors[j][k]) {
                        scores[i][j]++;
                    }
                }
            }
        }
        
        int maxScore = 0;
        vector<bool> used(m, false);
        
        function<void(int, int)> backtrack = [&](int student, int currentScore) {
            if (student == m) {
                maxScore = max(maxScore, currentScore);
                return;
            }
            
            for (int mentor = 0; mentor < m; mentor++) {
                if (!used[mentor]) {
                    used[mentor] = true;
                    backtrack(student + 1, currentScore + scores[student][mentor]);
                    used[mentor] = false;
                }
            }
        };
        
        backtrack(0, 0);
        return maxScore;
    }
};

class Solution:
    def maxCompatibilitySum(self, students: List[List[int]], mentors: List[List[int]]) -> int:
        m, n = len(students), len(students[0])
        
        # 预计算兼容性评分矩阵
        scores = [[0] * m for _ in range(m)]
        for i in range(m):
            for j in range(m):
                for k in range(n):
                    if students[i][k] == mentors[j][k]:
                        scores[i][j] += 1
        
        max_score = 0
        used = [False] * m
        
        def backtrack(student, current_score):
            nonlocal max_score
            if student == m:
                max_score = max(max_score, current_score)
                return
            
            for mentor in range(m):
                if not used[mentor]:
                    used[mentor] = True
                    backtrack(student + 1, current_score + scores[student][mentor])
                    used[mentor] = False
        
        backtrack(0, 0)
        return max_score

public class Solution {
    public int MaxCompatibilitySum(int[][] students, int[][] mentors) {
        int m = students.Length, n = students[0].Length;
        
        // 预计算兼容性评分矩阵
        int[,] scores = new int[m, m];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < m; j++) {
                for (int k = 0; k < n; k++) {
                    if (students[i][k] == mentors[j][k]) {
                        scores[i, j]++;
                    }
                }
            }
        }
        
        int maxScore = 0;
        bool[] used = new bool[m];
        
        void Backtrack(int student, int currentScore) {
            if (student == m) {
                maxScore = Math.Max(maxScore, currentScore);
                return;
            }
            
            for (int mentor = 0; mentor < m; mentor++) {
                if (!used[mentor]) {
                    used[mentor] = true;
                    Backtrack(student + 1, currentScore + scores[student, mentor]);
                    used[mentor] = false;
                }
            }
        }
        
        Backtrack(0, 0);
        return maxScore;
    }
}

var maxCompatibilitySum = function(students, mentors) {
    const m = students.length;
    const n = students[0].length;
    
    // Precompute compatibility scores
    const scores = Array(m).fill().map(() => Array(m).fill(0));
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < m; j++) {
            for (let k = 0; k < n; k++) {
                if (students[i][k] === mentors[j][k]) {
                    scores[i][j]++;
                }
            }
        }
    }
    
    // Backtrack to find maximum sum
    function backtrack(studentIndex, usedMentors) {
        if (studentIndex === m) {
            return 0;
        }
        
        let maxScore = 0;
        for (let mentorIndex = 0; mentorIndex < m; mentorIndex++) {
            if (!usedMentors.has(mentorIndex)) {
                usedMentors.add(mentorIndex);
                const currentScore = scores[studentIndex][mentorIndex] + 
                                   backtrack(studentIndex + 1, usedMentors);
                maxScore = Math.max(maxScore, currentScore);
                usedMentors.delete(mentorIndex);
            }
        }
        
        return maxScore;
    }
    
    return backtrack(0, new Set());
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度分析
时间复杂度O(m! + m²n)
空间复杂度O(m²)

说明：

  • 时间复杂度：预计算兼容性矩阵需要 O(m²n)，回溯算法需要遍历所有排列，最坏情况下为 O(m!)
  • 空间复杂度：需要存储 m×m 的兼容性评分矩阵，递归调用栈深度为 O(m)