题目描述
思路解析动画文字版
记牢这两步:先把每一对的评分算成表 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 · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题