LeetCode 1947中等动态规划
最大兼容性评分和 图解题解
这道题到底在问什么
给定学生答案 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
- 输入
- students=[[0,0],[0,0],[0,0]], mentors=[[1,1],[1,1],[1,1]]
- 输出
- 0
先想最直接的笨办法
记牢这两步:先把每一对的评分算成表 g,再回溯枚举所有一一配对取最大和。下面先把 g 一格一格填出来。（动画第 3 步）
最优解：一步一步想明白
- 3记牢这两步:先把每一对的评分算成表 g,再回溯枚举所有一一配对取最大和。下面先把 g 一格一格填出来。
- 4每行一名学生这是三名学生的答卷,每一行是一名学生对三道题的作答,格子里是 0 或 1。学生 0 答的是 1、1、0,学生 1 答 1、0、1,学生 2 答 0、0、1。等会儿要拿它逐行去和导师比。
- 5每行一名导师这是三名导师的答卷。导师 0 答 1、0、0,导师 1 答 0、0、1,导师 2 答 1、1、0。兼容性评分就是把某个学生这一行和某个导师这一行,逐题对齐比一比,数出相同的题数。
- 6先把一张 3 行 3 列的空表 g 摆出来。行是学生、列是导师,第 i 行第 j 列这一格,填的就是学生 i 和导师 j 答案相同的题数。接下来一格一格填,填法就是把对应的两行答案逐题比对、数相同的个数。
- 7算学生 0 和导师 0。学生 0 答 1、1、0,导师 0 答 1、0、0,三道题逐个对:第1题 相同、第2题 不同、第3题 相同,相同的有 2 道,所以 g[0][0] 填 2。
- 8算学生 0 和导师 1。学生 0 答 1、1、0,导师 1 答 0、0、1,三道题逐个对:第1题 不同、第2题 不同、第3题 不同,相同的有 0 道,所以 g[0][1] 填 0。
- 9算学生 0 和导师 2。学生 0 答 1、1、0,导师 2 答 1、1、0,三道题逐个对:第1题 相同、第2题 相同、第3题 相同,相同的有 3 道,所以 g[0][2] 填 3。
- 10算学生 1 和导师 0。学生 1 答 1、0、1,导师 0 答 1、0、0,三道题逐个对:第1题 相同、第2题 相同、第3题 不同,相同的有 2 道,所以 g[1][0] 填 2。
- 11算学生 1 和导师 1。学生 1 答 1、0、1,导师 1 答 0、0、1,三道题逐个对:第1题 不同、第2题 相同、第3题 相同,相同的有 2 道,所以 g[1][1] 填 2。
- 12算学生 1 和导师 2。学生 1 答 1、0、1,导师 2 答 1、1、0,三道题逐个对:第1题 相同、第2题 不同、第3题 不同,相同的有 1 道,所以 g[1][2] 填 1。
- 13算学生 2 和导师 0。学生 2 答 0、0、1,导师 0 答 1、0、0,三道题逐个对:第1题 不同、第2题 相同、第3题 不同,相同的有 1 道,所以 g[2][0] 填 1。
- 14算学生 2 和导师 1。学生 2 答 0、0、1,导师 1 答 0、0、1,三道题逐个对:第1题 相同、第2题 相同、第3题 相同,相同的有 3 道,所以 g[2][1] 填 3。
- 15算学生 2 和导师 2。学生 2 答 0、0、1,导师 2 答 1、1、0,三道题逐个对:第1题 不同、第2题 不同、第3题 不同,相同的有 0 道,所以 g[2][2] 填 0。
- 16九格全部填好,兼容矩阵 g 出炉。往后配对时想知道某个学生配某个导师值几分,直接查这张表就行,不用再逐题比。这些分数有高有低,配对要看整体搭法,不能只贪当前一格。下面进入第二步:枚举所有一一配对,找评分和最大的那种。
- 17开枚举 · 给学生 0、1、2 各配一个空闲导师
- 18学生 0 配 导师 0 · 得 g[0][0] = 2
- 19学生 1 配 导师 1 · 累计 2 + g[1][1] = 4
- 20学生 2 只剩 导师 2 · 方案 [M0,M1,M2] 评分和 = 4
- 21回退学生 1 · 改配 导师 2 · 累计 2 + g[1][2] = 3
- 22学生 2 配 导师 1 · 方案 [M0,M2,M1] 评分和 = 6
- 23回到学生 0 · 改配 导师 1 · 起手只有 g[0][1] = 0
- 24这一大类两种方案 · [M1,M0,M2] 与 [M1,M2,M0] 都只有 2
- 25回到学生 0 · 改配 导师 2 · 起手 g[0][2] = 3
- 26学生 1 配 导师 0 · 累计 3 + g[1][0] = 5
- 27学生 2 配 导师 1 · 方案 [M2,M0,M1] 评分和 = 8 · 最大值刷新
- 28回退学生 1 · 改配 导师 1 · 累计 3 + g[1][1] = 5
- 29学生 2 配 导师 0 · 方案 [M2,M1,M0] 评分和 = 6
- 30六种一一配对全枚举完 · 最大评分和 = 8
⚠️ 容易写错的地方
✗ 错：让每个学生各自贪心挑当前评分最高的空闲导师
✓ 对：回溯枚举所有一一配对,取评分和最大的一种
局部最优不等于全局最大,一个学生抢走某导师会连累后面的人,贪心在有些数据上会错过最优解
✗ 错：递归返回后忘了把 vis[j] 置回 false
✓ 对：回来立刻撤销占用标记
不撤销,这个导师会被后续分支当成永久占用,漏掉一大批本可行的配对方案
✗ 错：在 dfs 里每次都重新逐题数相同个数
✓ 对：开局先把兼容矩阵 g 预处理好,配对时直接查表
评分会被反复重算 m 的阶乘次,预处理一次存下来能省掉大量重复比较
✗ 错：把学生和导师当成可以多对一
✓ 对：学生导师是一一配对,每个导师只配一名学生
用 vis 保证每个导师只被占用一次,才符合双射的题意
完整代码（Python / C++ / Java）
Python
from __future__ import annotations
from 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 = right
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
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 ansC++
#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
struct ListNode {
int val;
ListNode *next;
ListNode() : val(0), next(nullptr) {}
ListNode(int x) : val(x), next(nullptr) {}
ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution {
public:
int maxCompatibilitySum(vector<vector<int>>& students, vector<vector<int>>& mentors) {
int m = students.size();
int n = students[0].size();
vector<vector<int>> g(m, vector<int>(m));
vector<bool> vis(m);
for (int i = 0; i < m; ++i) {
for (int j = 0; j < m; ++j) {
for (int k = 0; k < n; ++k) {
g[i][j] += students[i][k] == mentors[j][k];
}
}
}
int ans = 0;
function<void(int, int)> dfs = [&]( int i, int s ) {
if (i >= m) {
ans = max(ans, s);
return;
}
for (int j = 0; j < m; ++j) {
if (!vis[j]) {
vis[j] = true;
dfs(i + 1, s + g[i][j]);
vis[j] = false;
}
}
};
dfs(0, 0);
return ans;
}
};Java
import java.util.*;
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val, TreeNode left, TreeNode right){this.val=val;this.left=left;this.right=right;} }
class ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
class Solution {
private int m;
private int ans;
private int[][] g;
private boolean[] vis;
public int maxCompatibilitySum(int[][] students, int[][] mentors) {
m = students.length;
g = new int[m][m];
vis = new boolean[m];
for (int i = 0; i < m; ++i) {
for (int j = 0; j < m; ++j) {
for (int k = 0; k < students[i].length; ++k) {
if (students[i][k] == mentors[j][k]) {
++g[i][j];
}
}
}
}
dfs(0, 0);
return ans;
}
private void dfs(int i, int s) {
if (i >= m) {
ans = Math.max(ans, s);
return;
}
for (int j = 0; j < m; ++j) {
if (!vis[j]) {
vis[j] = true;
dfs(i + 1, s + g[i][j]);
vis[j] = false;
}
}
}
}复杂度
时间
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)
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 最大兼容性评分和 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
m 最大是 8,直接全排列枚举会不会超时?+
不会。八名学生配八名导师是 8 的阶乘,四万多种,每种沿途累加约 8 步,加上建兼容矩阵的 8 乘 8 乘 8,总量几十万次运算,毫秒级就跑完。所以小规模下直接回溯暴搜是完全可以接受的。
除了回溯,还有什么更快的解法?+
常见的是状压动态规划:用一个位掩码记录哪些导师已经被占用,状态是「前 i 个学生用掉了某个导师集合」的最大评分和,复杂度压到 O(2 的 m 次方 乘 m 乘 m)。再规范一点,这本质是二分图带权最大匹配,可以用匈牙利算法或 KM 算法解。本题数据小,回溯写起来最直接。
为什么要先建兼容矩阵 g,而不是边搜边算评分?+
因为同一对学生导师的评分,在枚举不同配对时会被反复用到。边搜边算的话,这个逐题比较会被重复做很多遍。预处理一次把所有 g[i][j] 存下来,搜索时直接查表是常数时间,把重复计算彻底省掉,是典型的空间换时间。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 最大兼容性评分和 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。