Bitmasking + DP
Intuition\nThe goal is to maximize the sum of selected cells in the grid, ensuring no two selected cells are from the same row and all selected values are uniqu
# Intuition\nThe goal is to maximize the sum of selected cells in the grid, ensuring no two selected cells are from the same row and all selected values are unique.\n\n# Approach\n- Mapping Numbers to Rows: Create a mapping of each unique number in the grid to the rows in which it appears.\n- Bitmasking: Represent the selected rows using a bitmask. Each bit in the mask indicates whether a particular row has been selected.\n- Recursive Function (`f1`): The function `f1` recursively computes the maximum score by either including or excluding the current number, ensuring the constraints are met.\n- DP: Use `f1tbl` to store the maximum score possible for each combination of rows selected and values considered. This helps avoid recomputation.\n\n# Complexity\n- Time complexity:\n`O(x * 2^m * m)`\nwhere,\nx: maximum number in the grid (100)\nm: no. of rows in grid\n\n- Space complexity:\n`O(x * 2^m)`\nwhere,\nx: maximum number in the grid (100)\nm: no. of rows in grid\n\n# Code\n```cpp []\ntypedef unordered_map<int, vector<int>> um;\nclass Solution {\npublic:\n    int m, n;\n    vector<vector<int>>f1tbl;\n    int maxScore(vector<vector<int>>& grid) {\n        m = grid.size();\n        n = grid[0].size();\n        f1tbl.resize(101, vector<int>(1 << m, -1));\n        unordered_map<int, vector<int>> num2row;\n        for (int i = 0; i < m; i++) {\n            for (int& num : grid[i]) {\n                num2row[num].push_back(i);\n            }\n        }\n\n        // mask of bit length 10 -> 1: row selected, 0: row not selected\n        int mask = 0;\n        return f1(100, mask, num2row);\n    }\n\n    int f1(int num, int& mask, um& num2row) {\n        if(f1tbl[num][mask] != -1) return f1tbl[num][mask];\n        if (num == 0) return f1tbl[num][mask] = 0;\n\n        int score = 0;\n\n        for (int r : num2row[num]) {\n            int rMask = (1 << r);\n            if (mask & rMask) continue;\n            mask |= rMask;\n            int newScore = num + f1(num - 1, mask, num2row);\n            score = max(newScore, score);\n            mask ^= rMask;\n        }\n\n        score = max(score, f1(num - 1, mask, num2row));\n\n        return f1tbl[num][mask] = score;\n    }\n};\n\n```
['Dynamic Programming', 'Bitmask', 'C++']