Hard

题目描述

给定一个由正整数组成的二维矩阵 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. 状态设计：使用位掩码 DP，其中状态 dp[mask] 表示当已经从某些行选择了单元格（用 mask 表示选择的行集合）时能获得的最大分数。

  3. 转移逻辑：对于每个值，我们尝试从所有包含该值的行中选择一个单元格。如果该行之前没有被选择过，就可以进行转移。

  4. 去重处理：由于要求选择的值唯一，我们按值分组处理。对于相同的值，我们需要选择能带来最大收益的那个位置。

算法流程：

  • 收集所有 (值, 行号) 对并按值降序排列
  • 按值分组，对于每组相同值，尝试所有可能的选择方案
  • 使用位掩码记录已选择的行，动态更新最大分数

时间复杂度主要由状态数量（2^行数）和每个状态的转移次数决定。

代码实现

class Solution {
public:
    int maxScore(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        
        // 收集所有值和位置
        vector<pair<int, int>> cells;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                cells.push_back({grid[i][j], i});
            }
        }
        
        // 按值降序排列
        sort(cells.begin(), cells.end(), greater<pair<int, int>>());
        
        // dp[mask] = 使用mask表示的行集合能获得的最大分数
        vector<int> dp(1 << m, 0);
        
        int i = 0;
        while (i < cells.size()) {
            int val = cells[i].first;
            vector<int> rows;
            
            // 收集所有值为val的行
            while (i < cells.size() && cells[i].first == val) {
                rows.push_back(cells[i].second);
                i++;
            }
            
            // 去重
            sort(rows.begin(), rows.end());
            rows.erase(unique(rows.begin(), rows.end()), rows.end());
            
            vector<int> newDp = dp;
            
            // 对于每个可用的行
            for (int row : rows) {
                for (int mask = 0; mask < (1 << m); mask++) {
                    if (!(mask & (1 << row))) { // 该行未被使用
                        newDp[mask | (1 << row)] = max(newDp[mask | (1 << row)], dp[mask] + val);
                    }
                }
            }
            
            dp = newDp;
        }
        
        return *max_element(dp.begin(), dp.end());
    }
};

class Solution:
    def maxScore(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        
        # 收集所有值和位置
        cells = []
        for i in range(m):
            for j in range(n):
                cells.append((grid[i][j], i))
        
        # 按值降序排列
        cells.sort(reverse=True)
        
        # dp[mask] = 使用mask表示的行集合能获得的最大分数
        dp = [0] * (1 << m)
        
        i = 0
        while i < len(cells):
            val = cells[i][0]
            rows = []
            
            # 收集所有值为val的行
            while i < len(cells) and cells[i][0] == val:
                rows.append(cells[i][1])
                i += 1
            
            # 去重
            rows = list(set(rows))
            
            new_dp = dp[:]
            
            # 对于每个可用的行
            for row in rows:
                for mask in range(1 << m):
                    if not (mask & (1 << row)):  # 该行未被使用
                        new_dp[mask | (1 << row)] = max(new_dp[mask | (1 << row)], dp[mask] + val)
            
            dp = new_dp
        
        return max(dp)

public class Solution {
    public int MaxScore(IList<IList<int>> grid) {
        int m = grid.Count, n = grid[0].Count;
        
        // 收集所有值和位置
        var cells = new List<(int val, int row)>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                cells.Add((grid[i][j], i));
            }
        }
        
        // 按值降序排列
        cells.Sort((a, b) => b.val.CompareTo(a.val));
        
        // dp[mask] = 使用mask表示的行集合能获得的最大分数
        int[] dp = new int[1 << m];
        
        int i = 0;
        while (i < cells.Count) {
            int val = cells[i].val;
            var rows = new List<int>();
            
            // 收集所有值为val的行
            while (i < cells.Count && cells[i].val == val) {
                rows.Add(cells[i].row);
                i++;
            }
            
            // 去重
            rows = rows.Distinct().ToList();
            
            int[] newDp = new int[1 << m];
            Array.Copy(dp, newDp, dp.Length);
            
            // 对于每个可用的行
            foreach (int row in rows) {
                for (int mask = 0; mask < (1 << m); mask++) {
                    if ((mask & (1 << row)) == 0) { // 该行未被使用
                        newDp[mask | (1 << row)] = Math.Max(newDp[mask | (1 << row)], dp[mask] + val);
                    }
                }
            }
            
            dp = newDp;
        }
        
        return dp.Max();
    }
}

var maxScore = function(grid) {
    const m = grid.length, n = grid[0].length;
    
    // 收集所有值和位置
    const cells = [];
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            cells.push([grid[i][j], i]);
        }
    }
    
    // 按值降序排列
    cells.sort((a, b) => b[0] - a[0]);
    
    // dp[mask] = 使用mask表示的行集合能获得的最大分数
    const dp = new Array(1 << m).fill(0);
    
    let i = 0;
    while (i < cells.length) {
        const val = cells[i][0];
        const rows = [];
        
        // 收集所有值为val的行
        while (i < cells.length && cells[i][0]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(V × 2^m × m)，其中 V 是不同值的数量，m 是行数。需要遍历所有不同的值，每个值需要更新 2^m 个状态，每次更新涉及 m 个行的选择
空间复杂度O(2^m)，需要存储 2^m 个状态的 DP 数组