DP C++
3276. Select Cells in Grid With Maximum Score\n\n### Description\n\nYou are given a 2D matrix grid consisting of positive integers.\n\nYou have to select one or
# [3276. Select Cells in Grid With Maximum Score](https://leetcode.com/problems/select-cells-in-grid-with-maximum-score/)\n\n### Description\n\nYou are given a 2D matrix `grid` consisting of positive integers.\n\nYou have to select *one or more* cells from the matrix such that the following conditions are satisfied:\n\n- No two selected cells are in the **same** row of the matrix.\n- The values in the set of selected cells are **unique**.\n\nYour score will be the **sum** of the values of the selected cells.\n\nReturn the **maximum** score you can achieve.\n\n \n\n**Example 1:**\n\n**Input:** grid = [[1,2,3],[4,3,2],[1,1,1]]\n\n**Output:** 8\n\n**Explanation:**\n\n![img](https://assets.leetcode.com/uploads/2024/07/29/grid1drawio.png)\n\nWe can select the cells with values 1, 3, and 4 that are colored above.\n\n**Example 2:**\n\n**Input:** grid = [[8,7,6],[8,3,2]]\n\n**Output:** 15\n\n**Explanation:**\n\n![img](https://assets.leetcode.com/uploads/2024/07/29/grid8_8drawio.png)\n\nWe can select the cells with values 7 and 8 that are colored above.\n\n \n\n**Constraints:**\n\n- `1 <= grid.length, grid[i].length <= 10`\n- `1 <= grid[i][j] <= 100`\n\n\n\n### Thought\n\n#### Approach 1\n\nWhen I first saw this question, I considered using a greedy approach to solve it. My initial idea was to sort the 2D matrix by sorting each row individually. If two rows have the same largest element, I would then sort them based on the difference between their elements, with the row having the larger difference coming first.\n\nSo every time I can choose the biggest element in each row. The code would be like below:\n\n```C++\nclass Solution {\npublic:\n    static bool customSort(const vector<int>& a, const vector<int>& b) {\n        int sumA = a[0] + a[1];\n        int sumB = b[0] + b[1];\n\n        if (sumA != sumB) {\n            return sumA < sumB; \n        } else {\n            int diffA = abs(a[0] - a[1]);\n            int diffB = abs(b[0] - b[1]);\n            return diffA > diffB; \n        }\n    }\n    int maxScore(vector<vector<int>>& grid) {\n        if (grid.size() == 1) {\n            sort(grid[0].begin(), grid[0].end(), greater<int>());\n            return grid[0][0];\n        } else if (grid[0].size() == 1) {\n            unordered_set<int> tmp;\n            for (auto& v : grid) {\n                tmp.insert(v[0]);\n            }\n            int ans = 0;\n            for (auto& i : tmp) ans += i;\n            return ans;\n        }\n        sort(grid.begin(), grid.end(), customSort);\n\n        int sum = 0;\n        unordered_set<int> s;\n        for (auto& v : grid) {\n            sort(v.begin(), v.end(), greater<int>());\n            for (int i = 0; i < v.size(); i++) {\n                if (s.find(v[i]) == s.end()) {\n                    s.insert(v[i]);\n                    sum += v[i];\n                    break;\n                }\n            }\n        }\n        return sum;\n    }\n};\n\n```\n\nHowever, if we use `[[16,18],[20,20],[18,18],[1,15]]` this case, we can find the array after sorting would be \n\n```\n1 15  \n\n16 18  \n\n18 18  \n\n20 20 \n```\n\nWe have to choose 15, 18, 18, 20. But we can not choose 18 twice time, so this method didn\'t work.\n\n#### Approach 2\n\nAs we can see the data constrain, it only have 10 rows maximum. So we can use an `n-bit` binary number to represent whether each row has been selected (referred to as the row\'s state)\n\nFor example, in a matrix with 3 rows, the state `101` indicates that the 1st and 3rd rows have been selected, while the 2nd row has not been selected.\n\n And when can get 2 conclusions from the problem:\n\n- we can only choose at most one element in each row\n- The number we choose in each row can not repeated\n\nSo we can define `dp[i]\\[j]`, which represent  the maximum score that can be obtained when the current number being considered is `i`, and the previously selected row information is represented by `j`\n\nIt has two scenarios:\n\n- If we can choose i, which means it appears in original grid.\n  - `dp[i][j] = dp[i+1][j]`\n- If we can not choose i\n  - `dp[i][j] = dp[i+1][(1 << k) | j] + i`\n\nSo the code would be like below:\n\n```C++\nclass Solution {\npublic:\n    int maxScore(vector<vector<int>>& grid) {\n        int m = grid.size();\n      \t// It represents num appears in grid\n        vector<vector<int>> g(m,vector<int>(101,0));\n        for (int i = 0; i < m; i++) {\n            for (auto& j : grid[i]) {\n                g[i][j] = 1;\n            }\n        }\n        vector<vector<int>> dp(105,vector<int>(1<<m,0));\n        for (int i = 100; i >= 1; i--) {\n          \t// Totally, it has 1 << m states\n            for (int j = 0; j < 1 << m; j++) {\n                dp[i][j] = dp[i+1][j];\n              \t// Enumerat all the rows\n                for (int k = 0; k < m; k++) {\n                  \t// (j >> k & 1): row k has been selected or not\n                  \t// grid[k][i]: in row k, it has num i or not\n                    if ((j >> k & 1) == 0 && g[k][i] == 1) {\n                      \t// (1 << k | j): make row k be selected  \n                        dp[i][j] = max(dp[i][j], dp[i + 1][1 << k | j] + i);\n                    }\n                }\n            }\n        }\n        return dp[1][0];\n    }\n};\n```\n\n#### Explanation of all bit operations\n\n- **1 << m**\n  - It has m rows in total, so it has `1 << m` states\n- **j >> k & 1**\n  - current state is `j`, shift the state `j` to the right by `k` positions, moving the bit corresponding to the `k-th` row to the least significant position.\n  - `& 1` which means judge the least significant position is 0 or 1, because both num equal to 1 can make the result equal to 1.\n- **1 << k | j**\n  - `1 << k` generate a binary number with only the `k-th` bit set to 1.\n  - `| j`, use OR operation to make `j` state `k-th` bit to 1, because any number `OR` 1 is 1, and `1` represent this row has been selected.\n\n
['C++']