DeepSeek LeetCode 3276. 选择矩阵中单元格的最大得分 Java实现

这道题是 LeetCode 3276，可以用状态压缩动态规划 (状压DP) 来解决。

核心思路

题目有两个核心限制：

1. 每行最多选一个：因为行数 n <= 10，可以用一个二进制整数（位掩码）表示哪些行已被占用。
2. 选中的值必须互不相同：可以从大到小考虑每个可能的数值（1 到 100），决定是否选择它。

状态定义与转移

· 状态定义：dp[i][mask] 表示处理完数值 i 到 100 后，已占用行状态为 mask 时能获得的最大得分。
· 初始状态：dp[101][mask] = 0（没有数值可选了）。
· 状态转移：对于数值 i，有两种选择：
1. 跳过：dp[i][mask] = dp[i+1][mask]
2. 选择：如果某行 r 未被占用且包含数值 i，则可以选它：dp[i][mask] = max(dp[i][mask], dp[i+1][mask | (1 << r)] + i)
· 最终答案：dp[1][0]（所有行都未被占用）。

Java 代码实现

```java
class Solution {
public int maxScore(List<List<Integer>> grid) {
int n = grid.size();
// 1. 预处理：记录每一行包含了哪些数字
// 数字范围是 1 到 100
boolean[][] has = new boolean[n][101];
for (int i = 0; i < n; i++) {
for (int v : grid.get(i)) {
has[i][v] = true;
}
}

// 2. 动态规划
// dp[i][mask]: 处理完数值 i..100，已选行状态为 mask 的最大得分
int[][] dp = new int[102][1 << n];

// 从大到小遍历所有可能的数值
for (int i = 100; i >= 1; i--) {
for (int mask = 0; mask < (1 << n); mask++) {
// 情况1: 不选择数字 i
dp[i][mask] = dp[i + 1][mask];

// 情况2: 选择数字 i，枚举它可以被安放在哪一行
for (int r = 0; r < n; r++) {
// 行 r 未被占用 且 行 r 包含数字 i
if ((mask & (1 << r)) == 0 && has[r][i]) {
int newMask = mask | (1 << r);
dp[i][mask] = Math.max(dp[i][mask], dp[i + 1][newMask] + i);
}
}
}
}

// 从数字1开始，初始没有任何行被占用
return dp[1][0];
}
}
```

复杂度分析

· 时间复杂度: O(100 * 2^n * n)，其中 n 是矩阵行数（n <= 10），因此效率很高。
· 空间复杂度: O(100 * 2^n)。

其他解法思路

· 回溯 + 剪枝：对每行去重排序，递归尝试选或不选，通过剪枝优化。
· 贪心 + TreeMap：从大到小处理数值，用 TreeMap 记录每个值出现在哪些行，用回溯处理冲突。

上述状态压缩DP是这道题比较标准的解法，逻辑清晰且易于实现。