Every day a Leetcode

题目来源：3276. 选择矩阵中单元格的最大得分

解法1：回溯

每一行最多选1个数字，如果要选，就要保证前面没有选择过该数字，然后将得分累加，传入下一次递归，如果不选，那就是直接跳过当前这一行，得分不累加。

代码：

/** @lc app=leetcode.cn id=3276 lang=cpp** [3276] 选择矩阵中单元格的最大得分*/// @lc code=start
class Solution
{
private:int m, n;int ans = 0;public:int maxScore(vector<vector<int>> &grid){m = grid.size(), n = m ? grid[0].size() : 0;unordered_set<int> s;backtrace(0, 0, s, grid);return ans;}// 辅函数 - 回溯void backtrace(int level, int score, unordered_set<int> s, vector<vector<int>> &grid){if (level == m){ans = max(ans, score);return;}for (int j = 0; j < n; j++){if (s.count(grid[level][j]) == 0){s.insert(grid[level][j]);score += grid[level][j];backtrace(level + 1, score, s, grid);score -= grid[level][j];s.erase(grid[level][j]);backtrace(level + 1, score, s, grid);}}}
};
// @lc code=end

结果：超时

复杂度分析：

时间复杂度：O(m * n * 2^m*n)，其中 m 和 n 分别为二维矩阵 grid 的行数和列数。

空间复杂度：O(m * n + 2^m)，其中 m 和 n 分别为二维矩阵 grid 的行数和列数。

解法2：状压 DP

定义状态为 dp[i][j]，表示在 [1,i] 中选数字，所选数字所处的行号不能在集合 j 中，每行至多一个数且没有相同元素时，所选元素之和的最大值。

讨论元素 i 选或不选：

• 不选 i，问题变成在 [1,i−1] 中选数字，所选数字所处的行号不能在集合 j 中，每行至多一个数且没有相同元素时，所选元素之和的最大值，即 dp[i-1][j]。
• 选 i，枚举选第 k 行的 i（提前预处理 i 所处的行号），问题变成在 [1,i−1] 中选数字（注意 i 只能选一次），所选数字所处的行号不能在集合 j∪{k} 中，每行至多一个数且没有相同元素时，所选元素之和的最大值，即 dp[i-1][j∪{k}]。

两种情况取最大值。

代码：

// 状压 DPclass Solution
{
public:int maxScore(vector<vector<int>> &grid){int m = grid.size();unordered_map<int, int> pos;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>> dp(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++){dp[i + 1][j] = dp[i][j]; // 不选 xfor (int t = pos[x], lb; t; t ^= lb){lb = t & -t;       // lb = 1<<k，其中 k 是行号if ((j & lb) == 0) // 没选过第 k 行的数{dp[i + 1][j] = max(dp[i + 1][j], dp[i][j | lb] + x); // 选第 k 行的 x}}}}return dp.back()[0];}
};

结果：

复杂度分析：

时间复杂度：O(m * n * 2^m)，其中 m 和 n 分别为二维矩阵 grid 的行数和列数。

空间复杂度：O(m * n + 2^m)，其中 m 和 n 分别为二维矩阵 grid 的行数和列数。