DP - Bitmask without sorting (Simple rundown from 100) || Well explained || Easy
Intuition\n Describe your first thoughts on how to solve this problem.  \nNoticing the constrains, my first thoughts were backtracking. Then I observed that not
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. --> \nNoticing the constrains, my first thoughts were backtracking. Then I observed that not only the size of the grid has a small cap but also the value at every cell is also capped at 100. This naturally steered me to a bitmask dp approach.\n# Approach\n<!-- Describe your approach to solving the problem. -->\nHash the rows `num` (value in a cell) in an unordered map. Later, we will iterate over these rows by marking each row as visited in the bitmask and call `func` recursively.\n\n`dp[i][j]` represents the total sum to number `i` with mask `j`. `i` ranges from 0 to 100 based on the question. `j` represents the row masked by 1 << row. Calculate the maximum by iterating through all the combinations of a number and the rows it is present in.\n\n## Breaking Condition:\nWe break when `num == 0` i.e. all numbers in the cell have been considered.\n\n**Important caution**: </br>Pass the map and grid by reference, else you will get a TLE. \nReason - When you pass by value, a copy of the variable is made which takes $O(n^2)$ time for each recursive call. Hence, the TC would rather become $O(n^3 * 2^n * 101)$ which would result in a TLE\n\n# Complexity\n- Time complexity: $O(n * 2^n * 101)$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $O(101*2^n)$\n# Code\n```cpp []\nclass Solution {\nprivate:\n    int dp[101][1025];    \n    int func(vector<vector<int>>& grid, int bitmask, int num, unordered_map<int, vector<int>>& mp) {\n        if(num == 0)\n            return 0;\n        if(dp[num][bitmask] != -1)\n            return dp[num][bitmask];\n\n        // If num does not exist in the grid\n        int res = func(grid, bitmask, num-1, mp);\n\n        for(auto row: mp[num]) {\n            // Skip if row has already been visited\n            if(bitmask >> row & 1)\n                continue;\n            res = max(res, num + func(grid, (bitmask | (1<<row)), num-1, mp));\n        }\n        return dp[num][bitmask] = res;\n    }\n\npublic:\n    int maxScore(vector<vector<int>>& grid) {\n        const int m = grid.size();\n        const int n = grid[0].size();\n        unordered_map<int, vector<int>> mp;\n        memset(dp, -1, sizeof(dp));\n        for(int i=0; i<m; ++i) {\n            for(int j=0; j<n; ++j) {\n                mp[grid[i][j]].push_back(i);\n            }\n        }\n        return func(grid, 0, 100, mp);\n    }\n};\n```\n\nPlease upvote if you found this helpful!\n\n![image.png](https://assets.leetcode.com/users/images/23c9f539-9f9a-414a-ba52-ce5c51140962_1725193419.3911104.png)\n\n
['Dynamic Programming', 'Bitmask', 'C++']