LeetCode 题解工作台
最大兼容性评分和
有一份由 n 个问题组成的调查问卷，每个问题的答案要么是 0 （no，否），要么是 1 （yes，是）。 这份调查问卷被分发给 m 名学生和 m 名导师，学生和导师的编号都是从 0 到 m - 1 。学生的答案用一个二维整数数组 students 表示，其中 students[i] 是一个整数数组，…
5
题型
7
代码语言
3
相关题
当前训练重点
中等 · 状态·转移·动态规划
答案摘要
我们可以先预处理出每个学生 和导师 之间的兼容性评分 ，然后使用回溯算法求解。 定义一个函数 $\textit{dfs}(i, s)$，其中 表示当前处理到第 个学生， 表示当前的兼容性评分和。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
有一份由 n 个问题组成的调查问卷，每个问题的答案要么是 0（no，否），要么是 1（yes，是）。
这份调查问卷被分发给 m 名学生和 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.lengthn == students[i].length == mentors[j].length1 <= m, n <= 8students[i][k]为0或1mentors[j][k]为0或1
解题思路
方法一：预处理 + 回溯
我们可以先预处理出每个学生 和导师 之间的兼容性评分 ，然后使用回溯算法求解。
定义一个函数 ，其中 表示当前处理到第 个学生， 表示当前的兼容性评分和。
在 中，如果 ，表示所有学生都已经分配完毕，此时更新答案为 。否则，我们枚举第 个学生可以分配给哪个导师，然后递归处理下一个学生。过程中，我们用一个数组 记录哪些导师已经被分配过，以避免重复分配。
我们调用 即可得到最大的兼容性评分和。
时间复杂度 ，空间复杂度 。其中 为学生和导师的数量。
class Solution:
def maxCompatibilitySum(
self, students: List[List[int]], mentors: List[List[int]]
) -> int:
def dfs(i: int, s: int):
if i >= m:
nonlocal ans
ans = max(ans, s)
return
for j in range(m):
if not vis[j]:
vis[j] = True
dfs(i + 1, s + g[i][j])
vis[j] = False
ans = 0
m = len(students)
vis = [False] * m
g = [[0] * m for _ in range(m)]
for i, x in enumerate(students):
for j, y in enumerate(mentors):
g[i][j] = sum(a == b for a, b in zip(x, y))
dfs(0, 0)
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(m * 2^m) due to DP over all mentor assignment states. Space complexity is O(2^m) for memoization of bitmask states. Precomputing compatibility scores adds O(m^2 * n). |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Notice the problem requires considering all possible student-mentor pairings for maximal total score.
- question_mark
State transition DP with bitmasking is expected for efficient solution due to small constraints (m <= 8).
- question_mark
Watch for repeated calculation of compatibility scores, which memoization or precomputation avoids.
常见陷阱
外企场景- error
Attempting brute-force permutations without memoization leads to factorial time complexity.
- error
Not precomputing compatibility scores can increase runtime and mask DP logic clarity.
- error
Incorrect bitmask updates can skip valid states or double-count mentors.
进阶变体
外企场景- arrow_right_alt
Maximize total compatibility when students or mentors can be left unassigned.
- arrow_right_alt
Allow multiple students per mentor and compute weighted compatibility scores.
- arrow_right_alt
Compute minimum total compatibility sum instead of maximum using similar DP state transitions.