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 <= 10
  • 1 <= grid[i][j] <= 100

动态规划：枚举值域，状压行号

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    public int maxScore(List<List<Integer>> grid) {
        int m = grid.size(), n = grid.get(0).size();
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < m; i++) {
            for (int x : grid.get(i)) {
                map.merge(x, 1 << i, (a, b) -> a | b);
            }
        }
        List<Integer> nums = new ArrayList<>(map.keySet());
        // f[i][j]: 用i从小到大遍历值域，用状压状态j表示已经选择的行号
        int f[][] = new int[nums.size()+1][1 << m];
        for (int i = 0; i < nums.size(); i++) {
            for (int j = 0; j < 1<<m; j++) {
                f[i+1][j] = Math.max(f[i+1][j], f[i][j]);  // j=11xx11表示全选
                // f[i+1][j] = f[i][j];  // j=00xx00表示全选
                for (int s = map.get(nums.get(i)), t = 0; s > 0; s -= t) {
                    t = s & -s;
                    if ((j & t) > 0) continue;
                    f[i+1][j|t] = Math.max(f[i+1][j|t], f[i][j] + nums.get(i));  // 乱序写入
                    // f[i+1][j] = Math.max(f[i+1][j], f[i][j|t] + nums.get(i));  // 顺序写入
                }
            }
        }
        return f[nums.size()][(1<<m) - 1];
        // return f[nums.size()][0];
    }
}

附带记忆化搜索：枚举值域作为状态，从大到小考虑每一个数，用状压行号作为另一个状态

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public int maxScore(List<List<Integer>> grid) {
        int m = grid.size(), n = grid.get(0).size();
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < m; i++) {
            for (int x : grid.get(i)) {
                map.merge(x, 1 << i, (a, b) -> a | b);
            }
        }
        List<Integer> nums = new ArrayList<>(map.keySet());
        int memo[][] = new int[nums.size()][1 << m];
        // for (int t[] : memo) Arrays.fill(t, -1);
        return dfs(nums.size()-1, 0, map, nums, grid, memo);
    }
    public int dfs(int i, int j, HashMap<Integer, Integer> map, List<Integer> nums, List<List<Integer>> grid, int memo[][]) {
        if (i < 0) return 0;
        if (memo[i][j] != 0) return memo[i][j];
        int res = dfs(i-1, j, map, nums, grid, memo);
        for (int k = map.get(nums.get(i)); k > 0; k -= (k & -k)) {
            if (((k & -k) & j) != 0) continue;
            res = Math.max(res, dfs(i-1, j | (k & -k), map, nums, grid, memo) + nums.get(i));
        }
        memo[i][j] = res;
        return res;
    }
}