题目描述
思路解析
一句话答案：LeetCode 1947 最大兼容性评分和：先把每对学生导师答案相同的题数算成 m×m 的 g 表，再回溯枚举全部一一配对取最大和。m≤8 时 m! 才四万多，全枚举跑得动，时间 O(m²·n+m·m!)、空间 O(m²)（g 表）。
学生和导师一一配对，评分和最大在求什么
students 和 mentors 各有 m 行，每行是一人对 n 道是非题的作答，只有 0 和 1。每名学生恰好配一名导师、每名导师只被配一次，一对的兼容性评分等于两人答案相同的题数，求所有配对方案里评分和的最大值。示例 students=[[1,1,0],[1,0,1],[0,0,1]]、mentors=[[1,0,0],[0,0,1],[1,1,0]]，答案是 8。
每人抢自己分最高的导师，为什么靠不住
一名学生抢走一名导师，后面所有人的选项都跟着变。本例按行贪心碰巧也凑到 8，可贪心（每步只挑眼前最高分）换一组答卷就没人担保。好在 m 最大 8，一一配对共 m! 种（第一人 m 种选、第二人剩 m−1 种…连乘）、8! 才 40320，全走一遍负担得起。真正的浪费在每种配对都现场逐题比答案：多乘一个 n，同一对人的分数被重比几千次。
为什么配对之前要先填一张 g 表
把比较和配对拆开：先建 m 行 m 列的兼容矩阵 g，g[i][j]（行是学生、列是导师，都从 0 数起）存学生 i 和导师 j 答案相同的题数。填表对 m×m 个组合各比 n 道题，O(m²·n)（大 O 记号，粗略记操作量和数据规模的关系）一次算清。之后谁配谁值几分，查表就行。
回溯凭什么把每种配对不重不漏走一遍
回溯（一条路走到底，退回来撤销选择再换下一条）按学生顺序推进：轮到学生 i，在没被占用的导师里挑一个 j，把 vis[j] 标成占用、当前和加上 g[i][j]，往下处理学生 i+1；走完退回来把 vis[j] 撤销，导师 j 才能进别的方案。i 走到 m 说明配齐，拿当前和刷新最大值。每层恰好定一名学生、vis 保证导师只被占一次，每条完整路径都是合法配对，m! 种各出现一次。
拿题面示例把 g 表和六种配对全算一遍
先填表。学生 0 答 1、1、0：和导师 0 的 1、0、0 有 2 题相同，和导师 1 的 0、0、1 全不同，和导师 2 的 1、1、0 全同，g 第 0 行是 2、0、3。同法算出学生 1 对三名导师是 2、2、1，学生 2 是 1、3、0。
再枚举六种配对，按学生 0、1、2 各配的导师记：[M0,M1,M2] 得 2+2+0=4，[M0,M2,M1] 得 2+1+3=6，[M1,M0,M2] 得 0+2+0=2，[M1,M2,M0] 得 0+1+1=2，[M2,M0,M1] 得 3+2+3=8，[M2,M1,M0] 得 3+2+1=6。最大 8，和题面输出对上。
vis 忘了撤销，答案为什么卡在 4 不动
第一条路 [M0,M1,M2] 走完得 4，回来不撤销 vis，三名导师全被永久占用，后面的分支全被跳过，答案卡在 4，比正确的 8 少一半。复杂度：建表 O(m²·n)，枚举 m! 种配对、每种沿途约 m 次加法，合计 O(m²·n+m·m!)；空间主要是 g 表的 O(m²)。第二组示例学生全答 0、导师全答 1，怎么配每对都 0 题相同，答案 0 就是合法输出。m 为 1 时只有一种配法，直接数那一对相同的题数，全同就拿满 n 分。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记牢这两步:先把每一对的评分算成表 g,再回溯枚举所有一一配对取最大和。下面先把 g 一格一格填出来。
学生答案 students · 3 名学生 × 3 道题：这是三名学生的答卷,每一行是一名学生对三道题的作答,格子里是 0 或 1。学生 0 答的是 1、1、0,学生 1 答 1、0、1,学生 2 答 0、0、1。等会儿要拿它逐行去和导师比。
导师答案 mentors · 3 名导师 × 3 道题：这是三名导师的答卷。导师 0 答 1、0、0,导师 1 答 0、0、1,导师 2 答 1、1、0。兼容性评分就是把某个学生这一行和某个导师这一行,逐题对齐比一比,数出相同的题数。
兼容矩阵 g · 先摆一张空表：先把一张 3 行 3 列的空表 g 摆出来。行是学生、列是导师,第 i 行第 j 列这一格,填的就是学生 i 和导师 j 答案相同的题数。接下来一格一格填,填法就是把对应的两行答案逐题比对、数相同的个数。
填 g[0][0] · 学生0 对 导师0：算学生 0 和导师 0。学生 0 答 1、1、0,导师 0 答 1、0、0,三道题逐个对:第1题 相同、第2题 不同、第3题 相同,相同的有 2 道,所以 g[0][0] 填 2。
填 g[0][1] · 学生0 对 导师1：算学生 0 和导师 1。学生 0 答 1、1、0,导师 1 答 0、0、1,三道题逐个对:第1题 不同、第2题 不同、第3题 不同,相同的有 0 道,所以 g[0][1] 填 0。
填 g[0][2] · 学生0 对 导师2：算学生 0 和导师 2。学生 0 答 1、1、0,导师 2 答 1、1、0,三道题逐个对:第1题 相同、第2题 相同、第3题 相同,相同的有 3 道,所以 g[0][2] 填 3。
填 g[1][0] · 学生1 对 导师0：算学生 1 和导师 0。学生 1 答 1、0、1,导师 0 答 1、0、0,三道题逐个对:第1题 相同、第2题 相同、第3题 不同,相同的有 2 道,所以 g[1][0] 填 2。
填 g[1][1] · 学生1 对 导师1：算学生 1 和导师 1。学生 1 答 1、0、1,导师 1 答 0、0、1,三道题逐个对:第1题 不同、第2题 相同、第3题 相同,相同的有 2 道,所以 g[1][1] 填 2。
填 g[1][2] · 学生1 对 导师2：算学生 1 和导师 2。学生 1 答 1、0、1,导师 2 答 1、1、0,三道题逐个对:第1题 相同、第2题 不同、第3题 不同,相同的有 1 道,所以 g[1][2] 填 1。
填 g[2][0] · 学生2 对 导师0：算学生 2 和导师 0。学生 2 答 0、0、1,导师 0 答 1、0、0,三道题逐个对:第1题 不同、第2题 相同、第3题 不同,相同的有 1 道,所以 g[2][0] 填 1。
填 g[2][1] · 学生2 对 导师1：算学生 2 和导师 1。学生 2 答 0、0、1,导师 1 答 0、0、1,三道题逐个对:第1题 相同、第2题 相同、第3题 相同,相同的有 3 道,所以 g[2][1] 填 3。
填 g[2][2] · 学生2 对 导师2：算学生 2 和导师 2。学生 2 答 0、0、1,导师 2 答 1、1、0,三道题逐个对:第1题 不同、第2题 不同、第3题 不同,相同的有 0 道,所以 g[2][2] 填 0。
兼容矩阵 g 填好 · 后面反复查它：九格全部填好,兼容矩阵 g 出炉。往后配对时想知道某个学生配某个导师值几分,直接查这张表就行,不用再逐题比。这些分数有高有低,配对要看整体搭法,不能只贪当前一格。下面进入第二步:枚举所有一一配对,找评分和最大的那种。
回溯开场 · 上排 M0 M1 M2 是三名导师：开枚举 · 给学生 0、1、2 各配一个空闲导师
学生 0 先试 导师 0：学生 0 配 导师 0 · 得 g[0][0] = 2
学生 1 试还空着的 导师 1：学生 1 配 导师 1 · 累计 2 + g[1][1] = 4
第一种配对到手,评分和 4：学生 2 只剩 导师 2 · 方案 [M0,M1,M2] 评分和 = 4
学生 1 换一个空闲导师：回退学生 1 · 改配 导师 2 · 累计 2 + g[1][2] = 3
第二种配对,评分和 6 刷新最好：学生 2 配 导师 1 · 方案 [M0,M2,M1] 评分和 = 6
学生 0 换第二个导师：回到学生 0 · 改配 导师 1 · 起手只有 g[0][1] = 0
学生 0 配 导师 1 · 两个叶子都是 2：这一大类两种方案 · [M1,M0,M2] 与 [M1,M2,M0] 都只有 2
学生 0 试最后一个导师：回到学生 0 · 改配 导师 2 · 起手 g[0][2] = 3
学生 1 先试 导师 0：学生 1 配 导师 0 · 累计 3 + g[1][0] = 5
第五种配对 · 评分和 8 登顶：学生 2 配 导师 1 · 方案 [M2,M0,M1] 评分和 = 8 · 最大值刷新
学生 1 换 导师 1 再看看：回退学生 1 · 改配 导师 1 · 累计 3 + g[1][1] = 5
第六种配对 · 评分和 6,不敌 8：学生 2 配 导师 0 · 方案 [M2,M1,M0] 评分和 = 6
回放 · 最优是 [M2,M0,M1] 得 8：六种一一配对全枚举完 · 最大评分和 = 8
边界想清:单对相同记满、答案全相反则任配都是 0、m 为 1 时只有一种配对直接算那一对。
面试重点:小规模回溯够用、可升级到状压 DP 或二分图匹配、预建兼容矩阵是空间换时间。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = rightclass ListNode: def __init__(self, val=0, next=None): self.val = val self.next = nextclass 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复杂度
- 时间：O(m·m·n + m·m!)，建兼容矩阵 g 要对 m 乘 m 个学生导师对、各比 n 道题,是 m 乘 m 乘 n;回溯枚举 m 的阶乘种一一配对,每种沿途累加约 m 步,是 m 乘 m 阶乘。m 最大 8 时阶乘四万多,整体几十万量级,能过
- 空间：O(m·m)，按峰值算。兼容矩阵 g 占 m 乘 m;vis 标记数组和递归栈深度都是 m 量级。峰值主要是那张 g 表,O(m 乘 m)
易错点
面试追问把动画讲成自己的话
追问m 最大是 8,直接全排列枚举会不会超时?
追问除了回溯,还有什么更快的解法?
追问为什么要先建兼容矩阵 g,而不是边搜边算评分?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
K 次调整数组大小浪费的最小总空间
LeetCode 1959 · 中等 · 沿着 动态规划套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题