最大兼容性评分和 图解题解

学生和导师一一配对，评分和最大在求什么

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 分。

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 ans

C++

#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;
            }
        }
    }
}