3276. 选择矩阵中单元格的最大得分
给你一个由正整数构成的二维矩阵 grid。
你需要从矩阵中选择 一个或多个 单元格，选中的单元格应满足以下条件：
你的得分为所选单元格值的总和。
返回你能获得的 最大 得分。
示例 1：
输入： grid = [[1,2,3],[4,3,2],[1,1,1]]
输出： 8
解释：
选择上图中用彩色标记的单元格，对应的值分别为 1、3 和 4 。
示例 2：
输入： grid = [[8,7,6],[8,3,2]]
输出： 15
解释：
选择上图中用彩色标记的单元格，对应的值分别为 7 和 8 。
提示：
1 <= grid.length, grid[i].length <= 101 <= grid[i][j] <= 100原站题解
golang 解法, 执行用时: 0 ms, 内存消耗: 4.3 MB, 提交时间: 2024-10-21 22:23:52
func maxScore1(grid [][]int) int {
pos := map[int]int{}
for i, row := range grid {
for _, x := range row {
// 保存所有包含 x 的行号（压缩成二进制数）
pos[x] |= 1 << i
}
}
allNums := make([]int, 0, len(pos))
for x := range pos {
allNums = append(allNums, x)
}
f := make([][]int, len(allNums)+1)
for i := range f {
f[i] = make([]int, 1<<len(grid))
}
for i, x := range allNums {
for j, v := range f[i] {
f[i+1][j] = v // 不选 x
for t, lb := pos[x], 0; t > 0; t ^= lb {
lb = t & -t // lb = 1<<k，其中 k 是行号
if j&lb == 0 { // 没选过第 k 行的数
f[i+1][j] = max(f[i+1][j], f[i][j|lb]+x) // 选第 k 行的 x
}
}
}
}
return f[len(allNums)][0]
}
func maxScore(grid [][]int) int {
pos := map[int]int{}
for i, row := range grid {
for _, x := range row {
// 保存所有包含 x 的行号（压缩成二进制数）
pos[x] |= 1 << i
}
}
f := make([]int, 1<<len(grid))
for x, posMask := range pos {
for j := range f {
for t, lb := posMask, 0; t > 0; t ^= lb {
lb = t & -t // lb = 1<<k，其中 k 是行号
if j&lb == 0 { // 没选过第 k 行的数
f[j] = max(f[j], f[j|lb]+x)
}
}
}
}
return f[0]
}
python3 解法, 执行用时: 262 ms, 内存消耗: 16.7 MB, 提交时间: 2024-10-21 22:23:25
class Solution:
def maxScore1(self, grid: List[List[int]]) -> int:
pos = defaultdict(list)
for i, row in enumerate(grid):
for x in set(row): # 去重
pos[x].append(i)
all_nums = list(pos)
u = 1 << len(grid)
f = [[0] * u for _ in range(len(all_nums) + 1)]
for i, x in enumerate(all_nums):
for j in range(u):
f[i + 1][j] = f[i][j] # 不选 x
for k in pos[x]:
if (j >> k & 1) == 0: # 没选过第 k 行的数
f[i + 1][j] = max(f[i + 1][j], f[i][j | 1 << k] + x) # 选第 k 行的 x
return f[-1][0]
def maxScore(self, grid: List[List[int]]) -> int:
pos = defaultdict(list)
for i, row in enumerate(grid):
for x in set(row): # 去重
pos[x].append(i)
u = 1 << len(grid)
f = [0] * u
for x, ps in pos.items():
for j in range(u):
for k in ps:
if (j >> k & 1) == 0:
f[j] = max(f[j], f[j | 1 << k] + x)
return f[0]
java 解法, 执行用时: 6 ms, 内存消耗: 41.4 MB, 提交时间: 2024-10-21 22:22:54
class Solution {
public int maxScore(List<List<Integer>> grid) {
Map<Integer, Integer> pos = new HashMap<>();
int m = grid.size();
for (int i = 0; i < m; i++) {
for (int x : grid.get(i)) {
// 保存所有包含 x 的行号（压缩成二进制数）
pos.merge(x, 1 << i, (a, b) -> a | b);
}
}
int u = 1 << m;
int[] f = new int[u];
for (Map.Entry<Integer, Integer> e : pos.entrySet()) {
int x = e.getKey();
int posMask = e.getValue();
for (int j = 0; j < u; j++) {
for (int t = posMask, lb; t > 0; t ^= lb) {
lb = t & -t; // lb = 1<<k，其中 k 是行号
if ((j & lb) == 0) { // 没选过第 k 行的数
f[j] = Math.max(f[j], f[j | lb] + x);
}
}
}
}
return f[0];
}
}
cpp 解法, 执行用时: 4 ms, 内存消耗: 21.2 MB, 提交时间: 2024-10-21 22:22:38
class Solution {
public:
// 记忆化搜索
int maxScore1(vector<vector<int>>& grid) {
unordered_map<int, int> pos;
int m = grid.size();
for (int i = 0; i < m; i++) {
for (int x : grid[i]) {
// 保存所有包含 x 的行号（压缩成二进制数）
pos[x] |= 1 << i;
}
}
vector<int> all_nums;
for (auto& [x, _] : pos) {
all_nums.push_back(x);
}
ranges::sort(all_nums); // 下面从大到小递归
int n = all_nums.size();
vector<vector<int>> memo(n, vector<int>(1 << m, -1)); // -1 表示没有计算过
auto dfs = [&](auto&& dfs, int i, int j) -> int {
if (i < 0) {
return 0;
}
int& res = memo[i][j]; // 注意这里是引用
if (res != -1) {
return res;
}
// 枚举选第 k 行的 x
int x = all_nums[i];
for (int t = pos[x], lb; t; t ^= lb) {
lb = t & -t; // lb = 1<<k，其中 k 是行号
if ((j & lb) == 0) { // 没选过第 k 行的数
res = max(res, dfs(dfs, i - 1, j | lb) + x);
}
}
if (res == -1) {
// 不选 x
res = dfs(dfs, i - 1, j);
}
return res;
};
return dfs(dfs, n - 1, 0);
}
// 递推
int maxScore2(vector<vector<int>>& grid) {
unordered_map<int, int> pos;
int m = grid.size();
for (int i = 0; i < m; i++) {
for (int x : grid[i]) {
// 保存所有包含 x 的行号（压缩成二进制数）
pos[x] |= 1 << i;
}
}
vector<int> all_nums;
for (auto& [x, _] : pos) {
all_nums.push_back(x);
}
int u = 1 << m;
vector<vector<int>> f(all_nums.size() + 1, vector<int>(u));
for (int i = 0; i < all_nums.size(); i++) {
int x = all_nums[i];
for (int j = 0; j < u; j++) {
f[i + 1][j] = f[i][j]; // 不选 x
for (int t = pos[x], lb; t; t ^= lb) {
lb = t & -t; // lb = 1<<k，其中 k 是行号
if ((j & lb) == 0) { // 没选过第 k 行的数
f[i + 1][j] = max(f[i + 1][j], f[i][j | lb] + x); // 选第 k 行的 x
}
}
}
}
return f.back()[0];
}
// 递推优化
int maxScore(vector<vector<int>>& grid) {
unordered_map<int, int> pos;
int m = grid.size();
for (int i = 0; i < m; i++) {
for (int x : grid[i]) {
// 保存所有包含 x 的行号（压缩成二进制数）
pos[x] |= 1 << i;
}
}
int u = 1 << m;
vector<int> f(u);
for (auto& [x, pos_mask] : pos) {
for (int j = 0; j < u; j++) {
for (int t = pos_mask, lb; t; t ^= lb) {
lb = t & -t; // lb = 1<<k，其中 k 是行号
if ((j & lb) == 0) { // 没选过第 k 行的数
f[j] = max(f[j], f[j | lb] + x);
}
}
}
}
return f[0];
}
};